Let's implement a classic algorithm: binary search on an array.
Implement a class named
BinarySearcher that provides one static method named
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
SearchList is a provided class. It provides a
get(int) method that returns the
Comparable at that index, and
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
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
- 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
end, at which point you can give up and return
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.