In java, 1. Implement a method that will search a given array using the linear s

Question

In java,

1. Implement a method that will search a given array using the linear search algorithm.

2. Implement a method that will search a given array using a recursive binary search algorithm.

Test the program for array sizes N = 16, 32, 64, 128, 256, 512, 1024, 2048, ......, 225. Initialize the array with random numbers between the ranges 1 through N and use the same array for testing linear search and binary search. Remember to sort the array before using binary search. Use a text file with 1,000 random numbers in the range 1 through 225 as the search keys.

Note that you have sort the input array before using the binary search algorithm, you can use any sort method available (e.g., sort method in the Java Collection Framework).

Update: the randomly generated numbers from 1 through N, cannot be repetitive.

the range is 1 through 225

Explanation / Answer

import java.io.*;
import java.util.*;

public class Demo16{

    public static void linearSearch(int[] data, int n){

       int found = 0;
       for (int i = 0; i<data.length; i++){
           if (n == data[i]){
              found = 1;
              System.out.println(n + " found at index " + i);
              break;
           }
       }
       if (found == 0)
          System.out.println(n + " not found ");
    }
    public static int binarySearch(int[] data, int l, int r, int n){
         if (r >= l){
             int mid = l + (r-l)/2;
             if (data[mid] == n)
                return mid;
             if (data[mid] < n)
                return binarySearch(data,mid+1,r,n);
             if (data[mid] > n)
                return binarySearch(data,l,mid-1,n);
         }
         return -1;
    }

    public static void main(String[] args){

        Random rand = new Random();
        int[] data = new int[10];
        int n;

        for (int i = 0; i<10; i++){
           data[i] = rand.nextInt(50);
        }
        System.out.println("Given array:");
        for (int i = 0; i<10; i++)
            System.out.print(data[i] + " ");
        System.out.println();
        n = data[5];
        System.out.println("Linear Search Result:");
        linearSearch(data,n);
        linearSearch(data,100);
      
        Arrays.sort(data);
        System.out.println("Sorted array:");
        for (int i = 0; i<10; i++)
            System.out.print(data[i] + " ");
        System.out.println();
        System.out.println("Binary Search Result:");
        int res = binarySearch(data,0,9,n);
        if (res == -1)
            System.out.println( n + " Not Found");
        else
            System.out.println(n + " found at index " + res);
        res = binarySearch(data,0,9,100);
        if (res == -1)
            System.out.println("100 not found");
        else
            System.out.println("100 found at index " + res);

    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.