Binary search is deceptively simple in concept but tricky in implementation. Off-by-one errors, wrong boundary conditions, and infinite loops are common pitfalls. The key insight: binary search is not just for sorted arrays — it applies to any problem where you can eliminate half the search space at each step. This guide covers the universal binary search template, classic patterns, and the most common interview problems.
The Universal Binary Search Template
Most binary search bugs come from inconsistent boundary handling. Use one template consistently: left = 0, right = len(arr) – 1. While left <= right: mid = left + (right – left) // 2 (avoids integer overflow vs (left + right) // 2). If arr[mid] == target: return mid. If arr[mid] target: right = mid – 1. If not found: return -1 (or left for insertion point). This template uses inclusive bounds [left, right]. The loop continues while left = target). Alternative: left = 0, right = len(arr) (exclusive right bound). While left < right: mid = left + (right – left) // 2. If condition: right = mid. Else: left = mid + 1. This template finds the leftmost position satisfying a condition. Choose one template and use it consistently. Do not mix conventions.
Pattern 1: Find Exact Value
Standard binary search in a sorted array. Given a sorted array, find the index of a target value. Apply the template directly. Time: O(log N). Variations: (1) First occurrence of target (lower bound): when arr[mid] == target, do not return immediately. Set right = mid – 1 and continue searching left. Record the position. After the loop, the recorded position is the first occurrence. (2) Last occurrence (upper bound): when arr[mid] == target, set left = mid + 1 and continue searching right. (3) Insertion point: return left after the loop ends without finding the target. This is the index where target would be inserted to maintain sorted order. Python bisect_left and bisect_right implement lower and upper bound respectively. In Java, Arrays.binarySearch returns the insertion point as -(insertionPoint) – 1 when the key is not found.
Pattern 2: Rotated Sorted Array
A sorted array rotated at an unknown pivot: [4,5,6,7,0,1,2]. The array is sorted in two halves. At each step, determine which half is sorted and whether the target is in that half. Algorithm: compute mid. Compare arr[mid] with arr[left] to determine which half is sorted. If arr[left] <= arr[mid] (left half is sorted): if arr[left] <= target < arr[mid], search left (right = mid – 1). Else search right (left = mid + 1). Else (right half is sorted): if arr[mid] < target arr[right], the minimum is in the right half (left = mid + 1). If arr[mid] <= arr[right], the minimum is in the left half or at mid (right = mid). When left == right, that is the minimum. With duplicates: if arr[mid] == arr[right], you cannot determine the sorted half. Shrink right by 1 (right–). Worst case becomes O(N).
Pattern 3: Binary Search on Answer (Search Space Reduction)
The most powerful binary search pattern: instead of searching in an array, binary search on the answer itself. The answer lies in a range [lo, hi]. For each candidate answer mid, check if it is feasible (satisfies the constraints). If feasible, try a better answer (search one half). If not feasible, search the other half. Koko Eating Bananas: Koko eats at speed K bananas per hour. Find the minimum K to finish all piles within H hours. Search space: K from 1 to max(piles). For each K, compute hours needed = sum(ceil(pile/K)). If hours <= H, K is feasible — try smaller (right = mid). Else try larger (left = mid + 1). Time: O(N * log(max_pile)). Split Array Largest Sum: split array into M subarrays to minimize the largest subarray sum. Search space: answer from max(arr) to sum(arr). For each candidate max_sum, greedily count how many subarrays are needed. If count <= M, feasible — try smaller. Else try larger. Capacity to Ship Packages: find minimum ship capacity to deliver all packages within D days. Same pattern — binary search on capacity, greedy check for feasibility. Recognition signal: "minimize the maximum" or "maximize the minimum" almost always means binary search on the answer.
Pattern 4: Binary Search on Matrices and Special Structures
Search in a 2D sorted matrix: (1) Matrix where each row and each column is sorted (rows are sorted left-to-right, columns top-to-bottom, but row ends may be larger than next row starts). Start from top-right corner. If target current, move down. Time: O(N + M). (2) Matrix where rows are sorted and the first element of each row is greater than the last element of the previous row. Treat as a 1D sorted array: index i maps to row = i / cols, col = i % cols. Standard binary search. Time: O(log(N*M)). Search in an infinite sorted array: you do not know the array length. Double the search range until you find an element >= target (start with range [0,1], then [0,2], [0,4], …). Then binary search within the found range. Time: O(log N) where N is the target position. Peak finding: find a peak element (greater than neighbors). Compare arr[mid] with arr[mid+1]. If arr[mid] < arr[mid+1], a peak exists to the right (left = mid + 1). Else a peak exists to the left or at mid (right = mid). Time: O(log N). This works because the problem guarantees at least one peak exists.
Common Pitfalls
Bugs that cause infinite loops or wrong answers: (1) Integer overflow: mid = (left + right) / 2 overflows for large values. Use mid = left + (right – left) / 2. (2) Wrong termination condition: left <= right for inclusive bounds, left < right for exclusive right bound. Mixing these causes off-by-one errors or infinite loops. (3) Not moving boundaries past mid: setting left = mid (instead of mid + 1) with integer division can cause an infinite loop when left == mid. Always move at least one step: left = mid + 1 or right = mid – 1. (4) Wrong comparison direction: for "find first occurrence," moving right = mid – 1 on match and continuing is correct. Returning immediately on match gives any occurrence, not the first. (5) Not handling empty array: check if the array is empty before starting. Practice: solve 15-20 binary search problems to build muscle memory with the template. The template should be automatic — you should not be thinking about boundary conditions during the interview.