BinarySearcher Array
Let's implement a classic algorithm: binary search on an array.
Implement a class named BinarySearcher
that provides one static method named search
.
search
takes a SearchList
as its first parameter and a Comparable
as its second.
If either parameter is null
, or if the SearchList
is empty, you should throw an IllegalArgumentException
.
SearchList
is a provided class. It provides a get(int)
method that returns the Comparable
at that index, and
a size
method that returns the size of the SearchList
. Those are the only two methods you should need!
search
returns a boolean
indicating whether the passed value
is located in the sorted SearchList
.
To search the sorted SearchList
efficiently, implement the following algorithm:
- Examine the value in the middle of the current array (index
(start + end) / 2
) - If the midpoint value is the value that we are looking for, return
true
- If the value that we are looking for is greater than the midpoint value, adjust the current array to start at the midpoint
- if the value that we are looking for is less than the midpoint value, adjust the current array to end at the midpoint
- Continue until you find the value, or until the
start
reaches theend
, at which point you can give up and returnfalse
This is a fun problem! Good luck! Keep in mind that every time you call SearchList.get
that counts as one
access, so you'll need to reduce unnecessary accesses to pass the test suite.