Lab 02
Recursive Binary Search
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
Else
mid ←
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)
EndIf
EndIf
return result
EndIf
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 binarySearch
-
params
-
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 search
-
params
-
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
All values match.
Upload the .java file to the dropbox
Make sure it conforms to the style guidelines