Why Binary Search Is Fundamental
Binary search is the backbone of efficient searching. Instead of scanning every element in O(n) time, it eliminates half the remaining candidates with every comparison, achieving O(log n) time. For an array of 1 billion elements, that's at most 30 comparisons instead of 1 billion.
- Sorted data: Any time an array is sorted (or has a monotonic property), binary search can reduce O(n) to O(log n).
- Search space reduction: Binary search doesn't just work on arrays — it works on any monotonic predicate. "Find the minimum capacity" or "find the first version that fails" are binary search problems.
- Off-by-one traps: Getting the boundaries right (
left <= rightvsleft < right,mid + 1vsmid) is where most candidates fail. Interviewers test your precision. - Frequency: Binary search appears in 15-20% of all LeetCode medium/hard problems — more than almost any other technique.
Classic Binary Search Template
The standard binary search finds a target value in a sorted array. The template uses two pointers left and right that converge toward the target. At each step, compute mid and compare it with the target to decide which half to discard.
left + (right - left) // 2 instead of (left + right) // 2?left + right can overflow if both are large integers. In Python, integers have arbitrary precision so overflow isn't an issue — but using this form is a good habit for interviews and shows you understand the pitfall.
Binary Search Step-by-Step
Let's trace binary search on the array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] searching for target 23. Each step halves the search space.
Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Left Boundary and Right Boundary Variants
The classic template finds any occurrence of the target. In interviews, you often need the first (leftmost) or last (rightmost) occurrence. These variants don't return immediately when they find the target — they keep narrowing the search space.
Left Boundary (First Occurrence)
Right Boundary (Last Occurrence)
arr[mid] == target. For the left boundary, move right = mid - 1 to keep searching left. For the right boundary, move left = mid + 1 to keep searching right.
Python's bisect Module
Python's standard library provides bisect_left and bisect_right — production-grade binary search functions implemented in C. They return the insertion point for a value in a sorted list.
bisect_left and bisect_right are cleaner, faster (C implementation), and less error-prone. Know both.
Binary Search on Answer
One of the most powerful (and non-obvious) applications of binary search is binary search on the answer. Instead of searching for a target in an array, you search over a range of possible answers and use a predicate function to determine if an answer is feasible.
The binary search on answer pattern works when:
- You need to find the minimum value that satisfies a condition (or the maximum that doesn't).
- The condition is monotonic: if value
xworks, then all values greater thanxalso work (or vice versa). - You can write a
feasible(x)function that returns True/False for a given candidate answer.
The template looks like this:
Problem: Search in Rotated Sorted Array
LeetCode 33. Given a sorted array that has been rotated at some pivot (e.g., [4,5,6,7,0,1,2]), search for a target in O(log n). The trick: at least one half of the array around mid is always sorted.
mid, one of the two halves [left..mid] or [mid..right] is always sorted. Check which half is sorted, then check if the target falls within that sorted range. If it does, search that half; otherwise, search the other half. This gives O(log n).
Problem: Find First and Last Position
LeetCode 34. Given a sorted array of integers, find the starting and ending position of a given target value. If the target is not found, return [-1, -1]. Must run in O(log n).
Problem: Integer Square Root
LeetCode 69. Given a non-negative integer x, return the integer part of its square root. This is a classic binary search on answer problem — find the largest integer n such that n * n <= x.
[1, x//2]. The predicate is mid*mid <= x. Since this predicate is monotonically decreasing (True for small mid, False for large mid), binary search finds the boundary efficiently in O(log x) time.
Problem: Find Peak Element
LeetCode 162. A peak element is strictly greater than its neighbors. Given an array where nums[i] != nums[i+1], find a peak element in O(log n). The array is not sorted — but binary search still works because of the monotonic "slope" property.
nums[-1] = nums[n] = -infinity (imaginary boundaries). This guarantees at least one peak exists. At any mid, if nums[mid] < nums[mid+1], the right half must contain a peak (ascending slope leading somewhere). Similarly for the left. This gives the monotonic property binary search needs.
Try It Yourself
First Bad Version (Binary Search on Answer)
You are a product manager. Versions 1 through n are released. One version is bad, and all versions after it are bad too. Given an API is_bad(version) that returns True if a version is bad, find the first bad version using the minimum number of API calls.
Constraint: There are n = 20 versions and version 13 is the first bad one. Use binary search to minimize calls to is_bad().
Challenge
You're given an m x n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. Search for a target value in O(log(m*n)).
Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 returns True.
m * n. Use standard binary search with index mapping: row = mid // n, col = mid % n. This lets you binary search over the "flattened" array without actually flattening it — O(log(m*n)) time, O(1) space.Koko has n piles of bananas. She can eat at speed k bananas per hour (one pile at a time, rounding up). Guards return in h hours. Find the minimum eating speed k so she finishes in time.
Example: piles = [3, 6, 7, 11], h = 8 returns k = 4.
k is [1, max(piles)]. For each candidate speed k, compute total hours needed: sum(ceil(p / k) for p in piles). If total hours <= h, then k is feasible — try smaller. Otherwise, try larger. Use math.ceil(p / k) or equivalently (p + k - 1) // k.Quiz
while left <= right, what happens when the target is not in the array?bisect_left([1, 3, 3, 3, 5], 3) return?Common Mistakes
- Off-by-one in loop condition. Using
while left < rightinstead ofwhile left <= rightin the classic template means you skip checking the last remaining element. The<=ensures the search space includes the case whereleft == right. - Infinite loop from wrong mid update. If you use
while left < rightwithleft = mid(instead ofmid + 1), you get an infinite loop whenleft + 1 == rightbecausemid = leftnever changes. Always move at least one step:left = mid + 1orright = mid - 1. - Integer overflow in mid calculation. In C++ and Java,
(left + right) / 2can overflow. Useleft + (right - left) / 2. Python doesn't overflow, but interviewers expect you to mention this. - Forgetting the sorted precondition. Binary search requires sorted data (or a monotonic property). If you apply it to an unsorted array without a valid reason (like peak element's slope property), you'll get wrong answers.
- Wrong boundary update for boundary variants. When finding the left boundary, you must set
right = mid - 1whenarr[mid] == target, not return immediately. Returning on the first match gives you any occurrence, not the first one.
Key Takeaways
- Classic binary search uses
while left <= rightand returns whenarr[mid] == target. Time: O(log n), Space: O(1). Master this template first — it's the foundation for all variants. - Boundary variants find the first or last occurrence by continuing the search even after finding the target. The only change: update
right = mid - 1(left boundary) orleft = mid + 1(right boundary) whenarr[mid] == target. - Python's bisect module provides
bisect_leftandbisect_right— use them in production code for clean, bug-free binary search. Count occurrences in O(log n) withbisect_right(x) - bisect_left(x). - Binary search on answer is the most powerful pattern: define a search space of possible answers, write a
feasible(x)predicate, and binary search for the boundary. Solves "minimize the maximum" / "maximize the minimum" problems. - Binary search works beyond sorted arrays — rotated arrays, peak elements, and any problem with a monotonic property. The key question: "Can I eliminate half the search space with one comparison?"
You've mastered binary search.
Now search for the right career move.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →