Binary Search

Notes

Skiena Chapter 4

See Algorithms/Search#Skiena Chapter 4 for some variations on binary search. Important aspects of this are repeated here:

• You can use binary search to find the starting point of a run of repeated keys, but you can also use a modified binary search (tends right, no equals) to return the right boundary of the run.
• Modified binary search (aforementioned, remove equals and tend right or tend left) can work as a "find greatest element less than this key" or "find least element greater than this key"
• One-sided binary search can be performed for a given key, looking for a nearby key, by a two-step process: first, the one-sided search window is progressively doubled - we look at the interval data[thisindex + 1], and if it is not greater than the key we are looking for, we look at data[thisindex + 2], then data[thisindex + 4], then data[thisindex + 8], then data[thisindex + 16], stopping when the key we examine is greater than the target key. We then perform a binary search using the lower and upper bounds. This runs with 2 log n operations max.

Modifications to Binary Search

We can make modifications to the binary search algorithm to perform other useful tasks like counting duplicates. See Binary Search Modifications page.