Synopsis Imagine you are given a collection of sorted data, and you want to find

Question

Synopsis

Imagine you are given a collection of sorted data, and you want to find the position of a particular item. The naïve way to do this would be to search the collection, one element at a time, from left to right. However, instead we can narrow down on the element in question very quickly by continuously dividing the array in halves, using the following algorithm:

Assume a sorted array, call it array

Assume a function that takes an array and gives back its length, called len

Assume a function that averages two numbers, called avg

/* @param array A sorted array
* @param target The number to find
* @param first The leftmost index to search (integer)
* @param last The rightmost index to search (inclusive, integer)
*/
Function Search(array, target, first, last)If first > last

// Number not found

Elsemid avg(first, last)
If target = array[mid]

result mid

ElseIf target < array[mid]

result Search(array, target, first, mid - 1)

Else

result Search(array, target, mid + 1, last)

EndIfEndIf
return resultEndIf

Specification

First, download the driver

Create a class BinarySearcher that contains the following static methods:

find Searches a sorted array (of integers) to see if it contains the given number. This method should have a call to binarySearchparams

array: The array (of integers) to search. Must be sorted.

number: The number to find within the array.

return The index of the given number, or -1 if it is not found.

binarySearch Uses binary search to recursively narrow in on the given element within an array. This method should be a helper method for searchparams

array: The array (of integers) to search. Must be sorted.

target: The number to find within the array.

first: The leftmost index to search from.

last: The rightmost index to search from (inclusive)

return The index of the target within the array, or -1 if it is not found.

You do not need a main method

Example Dialog:

Explanation / Answer

working java code

class BinarySearcher
{
public static void main(String args[])
{
    int c, first, last, middle, n, search, array[];

    Scanner in = new Scanner(System.in);
    System.out.println("Enter number of elements");
    n = in.nextInt();
    array = new int[n];

    System.out.println("Enter " + n + " integers");


    for (c = 0; c < n; c++)
      array[c] = in.nextInt();

    System.out.println("Enter value to find");
    search = in.nextInt();

    first = 0;
    last   = n - 1;
    middle = (first + last)/2;

    while( first <= last )
    {
      if ( array[middle] < search )
        first = middle + 1;  
      else if ( array[middle] == search )
      {
        System.out.println(search + " found at location " + (middle + 1) + ".");
        break;
      }
      else
         last = middle - 1;

      middle = (first + last)/2;
   }
   if ( first > last )
      System.out.println(search + " is not present in the list. ");
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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