# Binary Search

### From charlesreid1

# 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.

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |