Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target or applies the search condition to the middle value of the collection. If the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with an empty half, the condition cannot be fulfilled and target is not found.
Binary search can be implemented as an iterative algorithm (it could also be done recursively). It must maintain loop invariant i.e. valid search space as the algorithm progress i.e.
- Preconditions: Any assumptions that must be true about the input instance.
- Postconditions: The statement of what must be true when the algorithm/program returns.
- Exit condition: The statement of what must be true to exit a loop.
Most of Binary search problems will fall into 1 of these 3 templates.
Each of these 3 provided templates provide a specific use case:
Template #1 (left <= right):
- Search condition can be determined without comparing to the element’s neighbors (or use specific elements around it)
- No post-processing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found
Template #2 (left < right):
- Search condition needs to access element’s immediate right neighbor
- Use element’s right neighbor to determine if condition is met and decide whether to go left or right
- Search space is at least 2 in size at each step
- Post-processing required. Loop/Recursion ends when you have 1 element left.
Template #3 (left + 1 < right):
- Search condition needs to access element’s immediate left and right neighbors
- Use element’s neighbors to determine if condition is met and decide whether to go left or right
- Search Space is at least 3 in size at each step
- Post-processing required. Loop/Recursion ends when you have 2 elements left.