Complexity Analysis
Each comparison eliminates half the remaining elements. Doubling the input size adds just one more comparison. No extra memory beyond a few variables.
Recognize This Pattern When...
Pattern Signals
- Array is sorted (or can be treated as sorted, like a rotated sorted array)
- Problem requires O(log n) time complexity
- Searching for a specific value or finding a boundary
- Looking for the first/last occurrence of something
- Problem involves minimizing/maximizing a value that has a monotonic property
- Input size is large (10^5 or more) and linear scan would be too slow
Preconditions
- Data must be sorted or have a monotonic property (all "no" answers come before all "yes" answers)
- Random access is available (arrays work, linked lists don't)
- The search predicate must be monotonic: once it becomes true, it stays true
When NOT to Use
- Data is unsorted and sorting would change the answer (need original indices)
- Working with a linked list (no random access makes halving O(n))
- Need to find ALL occurrences (binary search finds one; modify to find boundaries)
- The search condition isn't monotonic (sometimes true, then false, then true again)
- Array is tiny (linear scan is simpler and equally fast for n < 50)
Why It Works
A sorted array has a useful property: every element to the left of position i is smaller than or equal to arr[i], and every element to the right is greater than or equal. When you check the middle element, you instantly know which half must contain your target. This halving process continues until you find the target or exhaust the search space.
The Analogy
Think about how you'd look up a word in a physical dictionary. You wouldn't start at page one and flip through every page. Instead, you open somewhere near the middle. If your word comes alphabetically before what you see, you focus on the left half. If it comes after, you focus on the right. A few strategic flips and you're there, having skipped most of the book entirely.
The Canonical Problem
Binary Search
easyGiven a sorted array of integers and a target value, return the index if the target is found. If not, return -1.
Solve on LeetCodeAlgorithm Template
Generic template you can adapt to most binary search problems.
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoids overflow
if arr[mid] == target:
return mid # Found it
elif arr[mid] < target:
left = mid + 1 # Target is in the right half
else:
right = mid - 1 # Target is in the left half
return -1 # Not foundImplementations
Complete examples with explanations. Copy-paste and adapt to your problem.
def binary_search(nums: list[int], target: int) -> int:
"""
Classic binary search with inclusive bounds [left, right].
Returns index of target, or -1 if not found.
Time: O(log n), Space: O(1)
"""
left = 0
right = 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
# Example usage
nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary_search(nums, target)) # 4
# ============================================================
# Half-open interval templates [lo, hi) - preferred for bounds
# ============================================================
def lower_bound(nums: list[int], x: int) -> int:
"""
First index where nums[i] >= x (or len(nums) if none).
Uses half-open interval [lo, hi).
Think: "where would x be inserted to maintain order?"
"""
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(nums: list[int], x: int) -> int:
"""
First index where nums[i] > x (or len(nums) if none).
Uses half-open interval [lo, hi).
Think: "where would x+epsilon be inserted?"
"""
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] <= x:
lo = mid + 1
else:
hi = mid
return lo
# Common patterns using lower/upper bound:
# - Count of x: upper_bound(x) - lower_bound(x)
# - First occurrence: lower_bound(x), check if nums[i] == x
# - Last occurrence: upper_bound(x) - 1, check if valid and == x
# - First > x: upper_bound(x)
# - Last <= x: upper_bound(x) - 1
# Variant: Find the leftmost (first) occurrence
def find_first(nums: list[int], target: int) -> int:
"""Find the first occurrence of target in a sorted array."""
left = 0
right = len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid # Record this match
right = mid - 1 # Keep searching left
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# Variant: Search Insert Position (where target should be inserted)
def search_insert(nums: list[int], target: int) -> int:
"""Return index where target is or should be inserted."""
left = 0
right = 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
# left is now the insertion point
return leftPython implementation with both inclusive [left, right] and half-open [lo, hi) templates. The lower_bound/upper_bound functions use half-open intervals and are the foundation for most boundary-finding problems. Includes variants for first occurrence and insertion position.
/**
* Classic binary search with inclusive bounds [left, right].
* Returns index of target, or -1 if not found.
*
* Time: O(log n), Space: O(1)
*/
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Example usage
const nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // 4
// Variant: Search in Rotated Sorted Array
function searchRotated(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
}
// Determine which half is sorted
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target in left sorted half
} else {
left = mid + 1; // Target in right half
}
} else {
// Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target in right sorted half
} else {
right = mid - 1; // Target in left half
}
}
}
return -1;
}JavaScript implementation with the classic algorithm plus the rotated array variant, which demonstrates how binary search adapts when the sorted property is partially disrupted.
Pattern Variations
First/Last Occurrence
O(log n) / O(1)When duplicates exist, find the leftmost or rightmost occurrence. Instead of returning immediately when found, continue searching in one direction while recording the match.
Search Insert Position
O(log n) / O(1)Find where an element is OR where it should be inserted to maintain sorted order. After the loop, the left pointer indicates the insertion point.
Rotated Sorted Array
O(log n) / O(1)Array was sorted then rotated at some pivot. One half is always fully sorted. Check which half is sorted, then determine if target lies within that half.
Binary Search on Answer
O(log(range) * verification) / O(1)When you can't search the array directly, binary search on the answer space instead. Key steps: (1) Identify lo/hi bounds as min/max possible answers (e.g., lo=1, hi=max(piles) for Koko). (2) Write a feasibility check that returns True if answer works - this MUST be monotonic (all False before all True, or vice versa). (3) Binary search until lo == hi, which is your answer. The check determines direction: if feasible, try smaller (hi = mid); if not, must go bigger (lo = mid + 1).
Lower Bound / Upper Bound
O(log n) / O(1)Half-open interval [lo, hi) templates that are the basis for most boundary searches. lower_bound finds first i where arr[i] >= x. upper_bound finds first i where arr[i] > x. Combining them: count of x = upper_bound(x) - lower_bound(x). Last occurrence = upper_bound(x) - 1. These match C++ STL and Python bisect semantics.
Practice Problems
| Problem | Difficulty | Type | Notes |
|---|---|---|---|
| Binary Search | easy | canonical | The textbook binary search problem - start here |
| Search Insert Position | easy | variant | Find element or its insertion point - tests boundary understanding |
| First Bad Version | easy | variant | Binary search with a predicate instead of value comparison |
| Find First and Last Position of Element in Sorted Array | medium | follow-up | Two binary searches to find both boundaries |
| Search in Rotated Sorted Array | medium | follow-up | Classic interview problem - identify the sorted half |
| Find Minimum in Rotated Sorted Array | medium | follow-up | Find the rotation point using binary search |
| Find Peak Element | medium | variant | Binary search without strict sorting - follow the ascending slope |
| Koko Eating Bananas | medium | follow-up | Binary search on the answer space, not the array itself |
| Capacity To Ship Packages Within D Days | medium | follow-up | Another binary search on answer - find minimum viable capacity |
| Median of Two Sorted Arrays | hard | follow-up | Advanced binary search - partitioning two arrays simultaneously |
Interview Tips
- Clarify whether the array has duplicates - this affects whether you need first/last occurrence logic
- Always use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow
- Draw the array and trace through an example when explaining - interviewers value clear communication
- Know both inclusive [left, right] and exclusive [left, right) templates, but be consistent within a problem
- For rotated arrays, explicitly state which half is sorted before deciding where to search
- When stuck, ask yourself: "What condition lets me eliminate half the search space?"
- Mention that binary search is O(log n) time and O(1) space - interviewers expect you to state complexity
- **Template Selector**: Exact match -> inclusive [left, right] with left <= right. First >= x (lower_bound) -> half-open [lo, hi) with lo < hi, hi = mid. Last <= x -> upper_bound - 1. Min x where predicate true -> answer-search with feasibility check. Rotated array -> determine which half is sorted first.
- **Debug Invariants**: Before submitting, verify: (1) Does the interval shrink every iteration? (2) Are you consistent about inclusive vs exclusive bounds? (3) Is your mid calculation biased correctly? Use (lo+hi)//2 when moving hi=mid, use (lo+hi+1)//2 when moving lo=mid.
Common Follow-up Questions
What if there are duplicates and you need the first occurrence?
CommonWhen you find the target, don't return immediately. Instead, record the index and continue searching leftward by setting right = mid - 1. The recorded index tracks the best answer found so far.
How would you handle a rotated sorted array?
CommonCompare nums[left] with nums[mid] to determine which half is sorted. If nums[left] <= nums[mid], the left half is sorted. Check if target falls within the sorted half's range. If yes, search there; if no, search the other half.
Can you implement binary search recursively?
CommonYes, pass left and right as parameters. Base case: left > right returns -1. Recursive case: compute mid, compare, and recurse on the appropriate half. Iterative is preferred in interviews since it uses O(1) space versus O(log n) stack space.
What if you need to find the closest element to target (not exact match)?
Run standard binary search. After the loop ends without finding target, left points to where target would be inserted. Compare nums[left] and nums[left-1] (with bounds checking) to find which is closer to target.
How do you apply binary search when you can't search the array directly?
CommonBinary search on the answer space. Define min and max possible answers, then binary search to find the smallest (or largest) answer where a feasibility check passes. Classic examples: Koko Eating Bananas, Ship Packages.
Common Mistakes
Integer overflow when calculating mid
# WRONG: Can overflow for large arrays
mid = (left + right) // 2 # left + right might exceed int max
# CORRECT: Overflow-safe calculation
mid = left + (right - left) // 2Fix: Always use left + (right - left) // 2 or left + (right - left) / 2 in languages without arbitrary precision integers. In Python this rarely matters, but it's a good habit for Java, C++, and JavaScript.
Off-by-one errors with boundary updates
# WRONG: Infinite loop when target not found
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid # Should be mid + 1
else:
right = mid # Should be mid - 1Fix: With inclusive bounds [left, right], always use left = mid + 1 and right = mid - 1 to exclude the just-checked element. Otherwise you'll check the same element repeatedly.
Using wrong comparison operator in loop condition
# WRONG: Misses single-element case
while left < right: # Exits when left == right
# ...
# This skips checking when the array narrows to one elementFix: With inclusive bounds, use while left <= right to handle the case where your target is the last remaining element. The < operator works with exclusive right bounds [left, right) but requires different update logic.
Forgetting to handle the "not found" case
# WRONG: Assumes target always exists
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 mid # mid is stale and meaningless hereFix: After the loop, return -1 (or your chosen sentinel) explicitly. Don't rely on mid - it points to the last element checked, not necessarily anything meaningful.
Mixing inclusive and half-open boundary updates
# WRONG: Using inclusive update (mid - 1) with half-open bounds
lo, hi = 0, len(nums) # half-open: hi is EXCLUSIVE
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1 # BUG: Should be hi = mid for half-open
# This skips elements! If mid=5 is a match, setting hi=4
# excludes index 5 from future consideration.Fix: With half-open [lo, hi), always use hi = mid (not mid - 1) because hi is already exclusive. The element at mid is naturally excluded since the interval becomes [lo, mid). Only use mid - 1 with inclusive bounds [left, right] where right is a valid index.
Frequently Asked Questions
Why is binary search O(log n) and what does that mean practically?
Each comparison cuts the remaining elements in half. Starting with n elements: after 1 step you have n/2, after 2 steps n/4, and so on. You need log₂(n) steps to reach 1 element. Practically, searching 1 billion elements takes only about 30 comparisons.
When should I use left <= right versus left < right?
Use left <= right with inclusive bounds where right points to a valid index (right = len(arr) - 1). Use left < right with exclusive bounds where right points past the last valid index (right = len(arr)). The inclusive style is more common in interviews and matches most textbook explanations. Pick one and stick with it.
Can binary search work on non-integer values?
Yes. For floating point answers (like finding a square root), use a tolerance check instead of exact equality. Loop while right - left > epsilon, and the final left or mid gives an approximate answer. You can also binary search on the iteration count for fixed precision.
How is binary search different from two pointers?
Binary search uses one moving pointer (mid) that jumps by halves, halving the search space each step. Two pointers uses two pointers that move incrementally toward each other, eliminating one element at a time. Binary search is O(log n); two pointers is O(n). Use binary search for finding a single element; two pointers for pair-related problems.
What is "binary search on the answer" and when do I use it?
Instead of searching an array for a value, you search a range of possible answers. Define the minimum and maximum possible answers, then binary search to find the best valid answer. Use it when: (1) you can check if an answer is feasible in O(n) or less, (2) the feasibility has a monotonic property (all invalid answers are on one side, all valid on the other). Classic examples: minimum speed to finish eating, minimum capacity to ship packages.
Why does binary search require sorted data?
The algorithm relies on knowing that all elements to the left of a value are smaller and all to the right are larger. This ordering lets you eliminate half the elements with one comparison. Without this guarantee, you can't know which half to discard. However, "sorted" can be generalized: binary search works on any monotonic predicate where answers switch from false to true at some point.