Test Writing: BinarySearcher Array (int)

Created By: Geoffrey Challen

/ Version: 2021.4.0

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. If the SearchList is empty you should throw an IllegalArgumentException.

SearchList is a provided class. It provides a get(Int) method that returns the Int at that index, and a 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: list[position].

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 the end, at which point you can give up and return false

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.

Test Design Challenge

You're challenge is to write tests for this problem described above.

• Provide a public class named TestBinarySearcher with a single non-private class method named test that accepts no arguments and does not return a value.
• If the implementation of the class described above is incorrect, your test method should throw an exception.
• If it is correct, do not throw an exception.
• You may want to use Kotlin's assert or check methods