Binary search is a core algorithm for finding values or boundaries in sorted data efficiently. This cheat sheet helps students compare the most common binary search variants and choose the correct loop pattern. It is useful for coding interviews, programming contests, and data structure problems where O(log n) reasoning matters.
The main goal is to prevent off-by-one errors by matching each variant to its invariant and return value.
The standard version searches for an exact target in a sorted array using mid = left + (right - left) // 2. Lower bound finds the first index where arr[i] >= target, while upper bound finds the first index where arr[i] > target. Binary search on answer searches a numeric range when a yes-or-no condition changes from false to true or true to false.
Correct binary search depends on a monotonic condition, careful boundary updates, and a clearly defined meaning for left and right.
Key Facts
- Standard binary search on a sorted array runs in O(log n) time because each step halves the remaining search interval.
- Use mid = left + (right - left) // 2 to avoid integer overflow in languages with fixed-size integers.
- For exact search with inclusive bounds, use left = 0, right = n - 1, and loop while left <= right.
- In exact search, if arr[mid] == target return mid, if arr[mid] < target set left = mid + 1, otherwise set right = mid - 1.
- Lower bound returns the first index i where arr[i] >= target, and it commonly uses left = 0, right = n with loop while left < right.
- Upper bound returns the first index i where arr[i] > target, and it also commonly uses left = 0, right = n with loop while left < right.
- Binary search on answer requires a monotonic predicate, meaning once condition(x) becomes true, it stays true for all larger x, or the reverse.
- When using a half-open interval [left, right), right is excluded, so returning left after the loop gives the first feasible boundary index.
Vocabulary
- Binary search
- An algorithm that repeatedly halves a sorted search space to find a value or boundary in logarithmic time.
- Invariant
- A condition that remains true before and after every loop iteration and explains why the algorithm is correct.
- Lower bound
- The first index in a sorted array where the value is greater than or equal to the target.
- Upper bound
- The first index in a sorted array where the value is strictly greater than the target.
- Monotonic predicate
- A true-or-false condition that changes direction at most once across the search range.
- Half-open interval
- An interval written as [left, right) that includes left but excludes right.
Common Mistakes to Avoid
- Using binary search on unsorted data is wrong because the comparison at mid does not reliably eliminate half of the array.
- Updating left = mid or right = mid in an inclusive exact search can cause an infinite loop because mid may not move when two elements remain.
- Confusing lower bound with upper bound gives the wrong duplicate position because lower bound uses arr[mid] >= target while upper bound uses arr[mid] > target.
- Returning mid after the loop is wrong for boundary searches because mid is only a temporary probe, while left usually stores the final boundary.
- Choosing the wrong loop condition, such as left <= right for a half-open [left, right) template, breaks the interval meaning and often causes out-of-range access.
Practice Questions
- 1 For arr = [2, 4, 6, 8, 10, 12] and target = 8, trace standard binary search and give the returned index.
- 2 For arr = [1, 2, 2, 2, 5, 7] and target = 2, find the lower bound index and the upper bound index.
- 3 A monotonic predicate possible(x) is false for x = 1, 2, 3 and true for x = 4, 5, 6, 7. Using binary search on [1, 7], what value should the first-true search return?
- 4 Explain why binary search on answer works for finding the minimum speed needed to finish tasks by a deadline, but not for a condition that switches between true and false many times.