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.
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e