BinarySearcher Array (int)
Let's implement a classic algorithm: binary search on an array.
Implement method named
search that takes a
SearchList as its first parameter and an
Int as its second.
SearchList is empty you should throw an
SearchList is a provided class. It provides a
get(Int) method that returns the
Int at that index, and
size method that returns the size of the
SearchList. Those are the only two methods you should need!
You can also access the list elements using bracket notation just like a list or array:
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 or use bracket notation
that counts as one access, so you'll need to reduce unnecessary accesses to pass the test suite.
Specifically, you should only call
list.get once per iteration, saving the result into a temporary variable.