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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the universal binary search template that prevents off-by-one errors?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use inclusive bounds consistently: left = 0, right = len(arr) – 1. While left <= right: mid = left + (right – left) // 2 (prevents overflow). If arr[mid] == target: return mid. If arr[mid] target: right = mid – 1. If not found: return -1 (or left for insertion point). Key rules: (1) Always move boundaries past mid (left = mid + 1 or right = mid – 1). Setting left = mid can cause infinite loops. (2) Use left <= right for the loop condition with inclusive bounds. (3) Use mid = left + (right – left) // 2 to prevent integer overflow. For finding first/last occurrence: on match, do not return immediately. For first: set right = mid – 1, record position, continue. For last: set left = mid + 1, record position, continue. Pick one template and use it for every binary search problem."}},{"@type":"Question","name":"What is binary search on answer and when should you use it?","acceptedAnswer":{"@type":"Answer","text":"Binary search on answer (search space reduction): instead of searching in an array, binary search on the answer value. The answer lies in a range [lo, hi]. For each candidate mid, check feasibility. If feasible, try a better answer. If not, try the other direction. Example — Koko Eating Bananas: find minimum eating speed K to finish piles in H hours. Search K from 1 to max(piles). For each K, compute hours = sum(ceil(pile/K)). If hours <= H, K works — try smaller. Else try larger. Time: O(N * log(max)). Recognition signal: minimize the maximum or maximize the minimum almost always means binary search on answer. Other examples: Split Array Largest Sum, Capacity to Ship Packages, Magnetic Force Between Balls. The pattern: define the search space of possible answers, write a feasibility check function, binary search for the optimal feasible answer."}},{"@type":"Question","name":"How do you search in a rotated sorted array?","acceptedAnswer":{"@type":"Answer","text":"A sorted array rotated at an unknown pivot: [4,5,6,7,0,1,2]. At each step, one half is sorted. Determine which half and whether the target is in it. Algorithm: compute mid. If arr[left] <= arr[mid], the left half [left..mid] is sorted. Check if target is in this range: if arr[left] <= target arr[mid], the right half [mid..right] is sorted. If arr[mid] < target arr[right], minimum is in right half. Else minimum is in left half or at mid. With duplicates: if arr[mid] == arr[right], cannot determine — shrink right by 1. Worst case O(N).”}},{“@type”:”Question”,”name”:”What are the most common binary search pitfalls?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Five pitfalls that cause bugs: (1) Integer overflow: (left + right) / 2 overflows for large values. Always use left + (right – left) / 2. (2) Infinite loops: setting left = mid (not mid + 1) with integer division when left == mid loops forever. Always move at least one step. (3) Wrong termination: left <= right for inclusive bounds, left < right for exclusive right. Mixing causes off-by-one or infinite loops. (4) Returning on first match: for first/last occurrence, returning immediately on match gives any occurrence. You must continue searching to find the boundary. (5) Wrong half selection in rotated array: comparing arr[mid] with arr[left] vs arr[right] determines which half is sorted. Getting this comparison wrong leads to incorrect results. Prevention: pick one template, practice it on 15-20 problems until the boundary handling is automatic. During interviews, trace through a small example to verify correctness before coding."}}]}