60% of Senior Devs Botch Binary Search. Here's the Fix.
You think you know binary search. Then the array isn't sorted, the bounds are off-by-one, or the "array" is actually a continuous answer space you have to invent. You freeze. About 60% of senior FAANG candidates write off-by-one bugs on their first binary search attempt during onsite, per our internal Discord-tracked dataset.
CS101 leaves you with a vague memory of "find the middle, compare, recurse" and zero memory of which loop condition, mid calculation, or update rule actually works. The bugs hide there.
This guide fixes both problems. Four hardened templates you copy-paste mentally (vanilla, lower-bound, upper-bound, and the underrated "binary search on answer") plus eighteen LeetCode walkthroughs covering every FAANG variant you'll see in 2026. By the end you'll have an off-by-one debugging cheat sheet that ends the infinite-loop trap.
Why binary search trips senior candidates
The "I know binary search" overconfidence trap is real. CS101 teaches binary search, leaving engineers with a vague memory of "find the middle, compare, recurse" and zero memory of which exact loop condition to use, which mid calculation avoids overflow, or how to update left/right without infinite-looping when left == right.
The three sources of binary search bugs:
- Wrong loop condition.
while left < rightandwhile left <= rightare not interchangeable. Pick a template, stick to it. - Wrong mid calculation.
mid = (left + right) // 2overflows in Java/C++ for large indices. Usemid = left + (right - left) // 2. - Wrong update of left/right. When the predicate is true at mid, do you set
right = midorright = mid - 1? Depends on whether you're looking for "first" or "any."
The fix: four templates, each with its own loop invariant and update rules. Don't mix them mid-problem.
TL;DR — the 4 templates
The four templates, scannable.
- Template 1: Vanilla binary search. Find an exact target.
while left <= right. Return -1 if not found. - Template 2: Lower bound. Leftmost index where
arr[i] >= target.while left < right. Returns insertion point. - Template 3: Upper bound. Leftmost index where
arr[i] > target. Same loop, slight predicate change. - Template 4: Binary search on answer. Search the answer space, not the array. Used for LC 875 (Koko), LC 1011 (Capacity), LC 410 (Split Array).
All four templates given below in Python, Java, and C++.
Template 1 — Vanilla binary search
The textbook template. Find an exact target in a sorted array.
Python:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Java:
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
C++:
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Loop invariant: target is in [left, right] if it exists. Termination: left > right.
Common bug: using mid = (left + right) / 2 in Java overflows when left + right > INT_MAX. Use the safe form left + (right - left) / 2 always.
Template 2 — Lower bound (leftmost >=)
Find the leftmost index where arr[i] >= target. Returns the insertion point if target is not present.
Python:
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
Loop invariant: answer is in [left, right]. Note: right = len(arr), NOT len(arr) - 1. Termination: left == right, return left.
Default to this template when you're not sure. It generalizes to upper bound and to binary search on answer with minor predicate tweaks. Equivalent to Python's bisect_left.
Template 3 — Upper bound (leftmost >)
Find the leftmost index where arr[i] > target. Same skeleton as Template 2, predicate arr[mid] <= target instead of <.
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
Equivalent to Python's bisect_right. The combination upper_bound - lower_bound gives the count of elements equal to target. Useful for LC 34.
Template 4 — Binary search on answer
The big unlock. When the question is "minimum X such that condition is true" or "maximum X such that condition is true", search the answer space, not the input array.
Binary search on answer is the most-underused interview pattern. If you spot "minimum/maximum X such that..." within 60 seconds, you've already solved it.
Algorithm: define a feasibility function feasible(x) that returns True if x is a valid answer. The feasible region is monotonic. If x is feasible, so are all larger (or smaller) values. Binary search the boundary.
Pseudo-code:
left, right = min_possible_answer, max_possible_answer
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid # mid works; try smaller
else:
left = mid + 1 # mid doesn't work; try larger
return left
The trick is identifying what to search over. Once you see "minimum X such that ..." or "maximum X such that ...", binary search on answer is on the table. Five worked examples below.
Problem 1 — Binary Search (LC 704)
Vanilla template. The warmup.
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Time: O(log n). Space: O(1).
Problem 2 — Search Insert Position (LC 35)
Lower bound template. The "where would I insert this" problem. Equivalent to bisect_left.
def searchInsert(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
Problem 3 — Find First and Last Position (LC 34)
Two binary searches: lower bound + upper bound. Most common follow-up to LC 35.
def searchRange(nums, target):
def lower(arr, t):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < t:
left = mid + 1
else:
right = mid
return left
first = lower(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
last = lower(nums, target + 1) - 1
return [first, last]
Time: O(log n). Space: O(1).
Problem 4 — Search in Rotated Sorted Array (LC 33)
The pivoted variant. Key insight: at any midpoint, at least one half is sorted. Find which half is sorted, then check if target falls in that sorted half.
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]: # left half sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
The 4-case decision tree (left-sorted-target-in-left, left-sorted-target-not-in-left, right-sorted-target-in-right, right-sorted-target-not-in-right) trips most candidates. Draw it on the whiteboard before coding. The interviewer notices.
Problem 5 — Find Minimum in Rotated Sorted Array (LC 153)
Find the rotation pivot using binary search.
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
Compare to right, not left. That makes the rotated case unambiguous. Comparing to left fails on the unrotated case [1,2,3,4,5].
Problem 6 — Median of Two Sorted Arrays (LC 4)
The textbook hard. O(log(min(m,n))) partition trick.
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = (total + 1) // 2
left, right = 0, m
while left <= right:
i = left + (right - left) // 2
j = half - i
nums1_left = nums1[i-1] if i > 0 else float('-inf')
nums1_right = nums1[i] if i < m else float('inf')
nums2_left = nums2[j-1] if j > 0 else float('-inf')
nums2_right = nums2[j] if j < n else float('inf')
if nums1_left <= nums2_right and nums2_left <= nums1_right:
if total % 2 == 0:
return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
return max(nums1_left, nums2_left)
elif nums1_left > nums2_right:
right = i - 1
else:
left = i + 1
This is the "final boss" of binary search. Don't get discouraged if it takes 5+ attempts to internalize. Even L6+ candidates rehearse this one cold the week before onsite.
For a deep-dive walkthrough, see LeetCode 4 Median of Two Sorted Arrays.
Time: O(log(min(m,n))). Space: O(1).
Problem 7 — Find Peak Element (LC 162)
The "binary search on unsorted array" surprise. The array isn't sorted but binary search works because the peak property is monotonic.
def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left
The insight: compare mid to mid+1. If nums[mid] > nums[mid+1], a peak is in [left, mid]. Otherwise it's in [mid+1, right]. The monotonic property is "is the slope going up or down at mid."
Problem 8 — Search a 2D Matrix (LC 74)
Treat as 1D binary search using arr[mid // n][mid % n].
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False
Problem 9 — Search a 2D Matrix II (LC 240)
NOT binary search. Use staircase walk from top-right or bottom-left in O(m+n).
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
else:
row += 1
return False
Why this is in the binary search pillar: candidates instinctively reach for binary search here, but the right tool is staircase walk. Knowing when NOT to use binary search is part of pattern recognition.
Problem 10 — Koko Eating Bananas (LC 875)
The flagship "binary search on answer" problem. Binary search on Koko's eating speed K.
import math
def minEatingSpeed(piles, h):
def feasible(K):
return sum(math.ceil(p / K) for p in piles) <= h
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
Feasibility: "can Koko finish in H hours at speed K?" Binary search smallest K. The answer space is [1, max(piles)] because at K = max(piles) Koko finishes in exactly len(piles) hours.
Time: O(n log max(piles)). Space: O(1).
Problem 11 — Capacity to Ship Packages Within D Days (LC 1011)
Same pattern as Koko but with sequential constraint. Binary search on ship capacity.
def shipWithinDays(weights, days):
def feasible(cap):
d = 1
cur = 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d <= days
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
The lower bound max(weights) matters. Capacity has to cover at least the heaviest package.
Problem 12 — Split Array Largest Sum (LC 410)
Hard variant of LC 1011. Binary search on the largest sum across m subarrays.
def splitArray(nums, m):
def feasible(max_sum):
count = 1
cur = 0
for n in nums:
if cur + n > max_sum:
count += 1
cur = 0
cur += n
return count <= m
left, right = max(nums), sum(nums)
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
Time: O(n log sum). Space: O(1).
Problem 13 — Find K Closest Elements (LC 658)
Sliding window OR binary search on the left endpoint of the window.
def findClosestElements(arr, k, x):
left, right = 0, len(arr) - k
while left < right:
mid = left + (right - left) // 2
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
return arr[left:left + k]
The compare predicate is the trick: distance from x to left edge vs distance to right edge of the would-be window.
Problem 14 — Time Based Key-Value Store (LC 981)
Binary search on timestamps within the per-key list.
class TimeMap:
def __init__(self):
self.store = {}
def set(self, key, value, timestamp):
if key not in self.store:
self.store[key] = []
self.store[key].append((timestamp, value))
def get(self, key, timestamp):
if key not in self.store:
return ""
arr = self.store[key]
left, right = 0, len(arr) - 1
result = ""
while left <= right:
mid = left + (right - left) // 2
if arr[mid][0] <= timestamp:
result = arr[mid][1]
left = mid + 1
else:
right = mid - 1
return result
Problem 15 — Aggressive Cows / Magnetic Force Between Two Balls (LC 1552)
Binary search on the maximum-of-minimum-distance. Classic binary-search-on-answer.
def maxDistance(position, m):
position.sort()
def feasible(d):
count = 1
last = position[0]
for p in position[1:]:
if p - last >= d:
count += 1
last = p
return count >= m
left, right = 1, position[-1] - position[0]
while left < right:
mid = left + (right - left + 1) // 2 # bias right for max-search
if feasible(mid):
left = mid
else:
right = mid - 1
return left
Bias-right mid calculation matters when searching for MAXIMUM feasible value. Drop the +1 and you infinite-loop when left = right - 1.
Problem 16 — Find K-th Smallest Pair Distance (LC 719)
Binary search on the distance value + 2-pointer feasibility check.
def smallestDistancePair(nums, k):
nums.sort()
def count_pairs(d):
count = left = 0
for right in range(len(nums)):
while nums[right] - nums[left] > d:
left += 1
count += right - left
return count
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_pairs(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
Two-pointer feasibility nested inside binary search on answer. Common L5+ Google question.
Problem 17 — Path with Minimum Effort (LC 1631)
Binary search on the answer + DFS feasibility check. (Or Dijkstra if you've covered graphs.)
def minimumEffortPath(heights):
m, n = len(heights), len(heights[0])
def feasible(threshold):
seen = {(0, 0)}
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if (r, c) == (m - 1, n - 1):
return True
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen:
if abs(heights[nr][nc] - heights[r][c]) <= threshold:
seen.add((nr, nc))
stack.append((nr, nc))
return False
lo, hi = 0, 10**6
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
Problem 18 — Maximum Number of Removable Characters (LC 1898)
Binary search on how many characters to remove + subsequence-check feasibility.
def maximumRemovals(s, p, removable):
def is_subsequence(removed_set):
i = 0
for j, c in enumerate(s):
if j in removed_set:
continue
if i < len(p) and p[i] == c:
i += 1
return i == len(p)
lo, hi = 0, len(removable)
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if is_subsequence(set(removable[:mid])):
lo = mid
else:
hi = mid - 1
return lo
The 4 sources of off-by-one bugs (and how to prevent them)
After watching candidates write binary search live for years, the same four bugs show up.
Bug 1: Wrong loop condition (< vs <=).
Vanilla template uses <= because target might be at right. Lower-bound template uses < because right is one past the last possible answer.
Fix: pick a template, stick to it, never mix.
Bug 2: Wrong mid calculation.
mid = (left + right) / 2 overflows in Java/C++.
Fix: always mid = left + (right - left) / 2. Memorize this form.
Bug 3: Wrong left/right update.
When predicate is true at mid, do you set right = mid or right = mid - 1?
Fix: derive from loop invariant, not intuition. If the loop is while left < right and answer might be at mid, use right = mid. If the loop is while left <= right and you've eliminated mid, use right = mid - 1.
Bug 4: Infinite loop when left == right.
Happens when neither pointer advances on a step.
Fix: ensure mid + 1 or mid - 1 advances at least one pointer per iteration. For maximum-feasible binary search, use mid = left + (right - left + 1) // 2 to bias right.
Debugging tip: trace through [0, 1] and [0, 1, 2] by hand before submitting. Two-element and three-element arrays expose 90% of off-by-one bugs.
When to use each template — the decision tree
- "Find exact target" → Template 1 (vanilla).
- "Find leftmost >= target" / "where would I insert" → Template 2 (lower bound).
- "Find leftmost > target" / "find first occurrence after" → Template 3 (upper bound).
- "Find min/max X such that condition" → Template 4 (binary search on answer).
2026 FAANG expectations
Interviewer expectations for binary search in 2026:
- Vanilla binary search writeable in under 3 minutes from scratch, off-by-one free.
- "Binary search on answer" pattern recognition for "minimum X" / "maximum X" problems within 60 seconds of reading the prompt.
- Comfort articulating loop invariant: "what's the invariant on left and right at each iteration?"
- Edge-case probes: "what if the array is empty?" "what if all elements equal target?" "what's your time complexity in terms of log of what?"
Practice plan — 18 problems in 2 weeks
- Week 1: Templates 1-3 + Problems 1-9.
- Week 2: Template 4 + Problems 10-18.
By end of week 2, all templates should be writeable from memory in under 5 minutes each.
For the parent pillar covering all 23 patterns FAANG draws from, see 23 LeetCode Patterns That Cover 95% of FAANG Questions. For the frequency-ranked problem list (binary search appears 8 times in the top 75), see 75 LeetCode Problems FAANG Asks Most.
FAQ
Why does my binary search infinite-loop?
You're updating left = mid or right = mid when you should advance by one. Fix: mid + 1 or mid - 1 on the appropriate side.
How do I know if a problem is binary-search-on-answer? Look for "minimum X such that" or "maximum X such that" framing where X is a number with a feasibility predicate.
Is binary search the same as bisect in Python?
Yes. bisect_left = lower bound, bisect_right = upper bound. Use the standard library when you can; write the loop when the interviewer asks you to.
What's the most asked binary search problem at FAANG? LC 33 (Search in Rotated Sorted Array) by frequency at Meta and Amazon. LC 4 (Median of Two Sorted Arrays) by frequency at Google L5+.
Should I use recursion or iteration for binary search? Iteration. Recursion adds stack overhead and the iterative form is cleaner. Exception: segment trees, where recursion is structurally cleaner.
The verdict
Binary search is four templates and one debugging discipline. Master the templates, internalize the off-by-one cheat sheet, and binary search becomes one of the fastest patterns to recognize and code in any FAANG loop.
If you found this useful, FaangCoder helps candidates iterate to optimal solutions in real interviews. It catches your off-by-one before the interviewer does. Try it on LC 4 to see how the partition trick breaks down step by step. $399 lifetime ($199/mo monthly option). See the Solve demo, Debug demo, or join the Discord.