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.
Understanding Binary Search Variants Reference
The hardest part of binary search is not calculating the middle position. It is proving that the answer has not been thrown away. This proof is called an invariant.
At the start of every loop, write down what must still be true about the current interval. For an exact search, the target can only be inside that interval if it exists. For a boundary search, every position before the interval fails the required test, while every position after it satisfies the test.
Each update must preserve that statement. If an update does not fit the statement, the loop may skip the answer or run forever.
Duplicates reveal why boundary versions are useful. Suppose a sorted list contains several copies of the same score. An exact search may return any one of them, depending on the middle positions chosen.
That is often not enough. The lower bound gives the insertion position before all equal scores. The upper bound gives the position after all equal scores.
Their difference is the number of copies. These two positions can be valid even when the target is absent. This makes them useful for keeping lists sorted, counting repeated values, and finding the full range of matching records.
Answer-space search works when the item being searched is not stored in an array. Imagine choosing the smallest truck capacity that can deliver all packages within a fixed number of days. For each possible capacity, a checking function simulates the deliveries.
Small capacities fail. From some capacity onward, all larger capacities succeed. The search is over possible capacities, not package positions.
Similar problems include the minimum time needed for machines to finish work, the largest minimum distance between placed objects, and the smallest possible maximum workload. The checking function is usually the real challenge. It must give a correct true or false result for every candidate.
Off-by-one mistakes usually come from mixing interval styles. An inclusive interval includes both ends, so removing the middle position requires moving an end past the middle. A half-open interval includes the left end but excludes the right end, so the right value may equal the list length.
Pick one style before writing code and keep it for the loop condition, middle update, and final return. Test tiny cases by hand.
Use an empty list, one item, a target below every item, a target above every item, and a list of identical values. These cases expose most errors because they force the search interval to shrink to its final one or zero positions.