Binary search is one of the most fundamental and powerful algorithms in computer science. It transforms O(n) linear searches into O(log n) logarithmic searches. It enables "binary search on answer" solutions to optimization problems that would otherwise seem intractable. And once you master it, you'll recognize it instantly in dozens of LeetCode problems.
But here's the challenge: binary search isn't just about finding an element in a sorted array—it's a family of techniques that extends to finding bounds, searching rotated arrays, 2D matrices, and even searching on answer spaces where no explicit array exists. Understanding when and how to apply each variant is what separates those who memorize solutions from those who truly master the pattern.
This comprehensive guide will teach you everything about binary search: all variants, when to use each pattern, the intuition behind why they work, common mistakes to avoid, and a systematic decision framework that works every time.
Binary search is a divide-and-conquer algorithm that repeatedly divides the search space in half until it finds the target or determines it doesn't exist.
The fundamental idea: Instead of checking every element linearly (O(n)), we eliminate half of the remaining elements with each comparison by leveraging the sorted property of the data.
Example:
Find 7 in: [1, 3, 5, 7, 9, 11, 13, 15, 17]
Step 1: Check middle (9)
7 < 9, so search left half: [1, 3, 5, 7]
Step 2: Check middle (3)
7 > 3, so search right half: [5, 7]
Step 3: Check middle (5)
7 > 5, so search right half: [7]
Step 4: Check middle (7)
7 == 7, found!
Total comparisons: 4 (vs 7 for linear search)The power of binary search comes from a simple mathematical insight:
If the data is sorted and we check the middle element, we can determine which half contains our target (if it exists) and discard the other half entirely.
This works because of the sorted property:
target < middle, target must be in the left half (all elements right of middle are ≥ middle)target > middle, target must be in the right half (all elements left of middle are ≤ middle)target == middle, we found itVisual proof:
Array: [1, 3, 5, 7, 9, 11, 13]
↑
mid=7
If target=5:
5 < 7, so target CANNOT be in [9, 11, 13]
We can safely discard the right half
If target=11:
11 > 7, so target CANNOT be in [1, 3, 5]
We can safely discard the left halfThis is why binary search works: the sorted property guarantees that eliminating half the search space is always safe.
Let's see the transformation from naive to optimal:
Linear search (O(n)):
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# Worst case: check all n elementsBinary search (O(log n)):
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
# Worst case: check log₂(n) elementsThe tradeoff: We require sorted data, but we get exponentially faster search.
Problem: Find an element in an array of size 1,000,000.
Linear search:
Binary search:
Result: Binary search is 50,000× faster on average, at the cost of requiring sorted data.
Binary search isn't one pattern—it's three distinct techniques that solve different types of problems. Understanding which variant to use is the key to mastering binary search.
The Pattern: Find the exact position of a target element in a sorted array.
When to use:
Why it works:
The sorted property allows us to eliminate half the search space with each comparison.
Visual representation:
Array: [1, 3, 5, 7, 9, 11, 13]
Target: 7
left=0, right=6, mid=3 → arr[3]=7 ✓ Found!Real-world analogy: Looking up a word in a dictionary. You don't start at page 1—you open to the middle, see if your word comes before or after, and repeat.
Example problems: Binary Search (#704), Search Insert Position (#35)
The Pattern: Binary search on the answer space to find the optimal value that satisfies a condition, using a "guess and check" approach.
When to use:
Why it works:
If we can verify whether a candidate answer is feasible, and feasibility is monotonic (if x works, x+1 also works OR x-1 also works), we can binary search on the answer space.
Visual representation:
Problem: Minimize the maximum (e.g., Koko Eating Bananas)
Answer space: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Feasibility: F F F F T T T T T T
↑
Find first T (minimum feasible)Real-world analogy: Finding the minimum internet speed needed to stream 4K video. You try different speeds (binary search) and check if the video buffers (feasibility check).
Example problems: Koko Eating Bananas (#875), Capacity To Ship Packages (#1011), Split Array Largest Sum (#410)
The Pattern: Apply binary search to arrays with special properties (rotated, 2D matrices, etc.) by identifying which portion maintains the sorted property.
When to use:
Why it works:
Even in rotated arrays, at least one half is always sorted. We can identify the sorted half and make decisions based on it.
Visual representation:
Rotated array: [7, 9, 11, 13, 1, 3, 5]
←sorted→ ←sorted→
At any mid point, one half is always sortedReal-world analogy: A circular bookshelf where books are in alphabetical order but the starting point is unknown. You can still find a book efficiently by identifying which section is in order.
Example problems: Search in Rotated Sorted Array (#33), Search a 2D Matrix (#74), Find Minimum in Rotated Sorted Array (#153)
Choosing the right pattern is crucial. Here's a systematic decision framework:
Question 1: What's the data structure?
├─ Sorted Array → Continue to Question 2
├─ Rotated Sorted Array → Rotated Binary Search ✓
├─ 2D Matrix (sorted properties) → 2D Binary Search ✓
├─ No explicit array, but answer space → Binary Search on Answer ✓
└─ Unsorted Array → Binary search NOT applicable (use hash map/linear)
Question 2: What's the goal?
├─ Find exact element → Classic Binary Search ✓
├─ Find first/last occurrence → Lower/Upper Bound ✓
├─ Minimize maximum / Maximize minimum → Binary Search on Answer ✓
├─ Find insertion position → Classic Binary Search variant ✓
└─ Find maximum/minimum element → May not need binary search
Question 3: Is there a monotonic property?
├─ Yes (sorted, or monotonic feasibility) → Binary Search ✓
├─ No → Binary search NOT applicable
└─ Unsure → Check if "if x works, does x+1 work?" or vice versa
Question 4: What's the time constraint?
├─ Need O(log n) → Binary Search ✓
├─ O(n) acceptable and data unsorted → Linear search
└─ Need O(1) → Binary search won't help (use hash map)Use Classic Binary Search when you see:
Use Binary Search on Answer when you see:
Use Rotated/Modified Binary Search when you see:
Don't use Binary Search when you see:
def binary_search(arr, target):
"""
For: Finding exact element in sorted array
Time: O(log n)
Space: O(1)
Returns: Index of target, or -1 if not found
"""
left, right = 0, len(arr) - 1
while left <= right:
# Avoid overflow: mid = (left + right) // 2 can overflow
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
# Target is in right half
left = mid + 1
else:
# Target is in left half
right = mid - 1
# Target not found
return -1JavaScript:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Java:
public int binarySearch(int[] arr, int target) {
int left = 0;
int 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;
}Lower Bound (First Occurrence):
def lower_bound(arr, target):
"""
For: Finding first occurrence of target (or insertion position)
Time: O(log n)
Space: O(1)
Returns: Index of first element >= target
"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
# First occurrence is in right half
left = mid + 1
else:
# arr[mid] >= target, could be the answer
# Keep searching left for earlier occurrence
right = mid
return leftUpper Bound (Last Occurrence):
def upper_bound(arr, target):
"""
For: Finding last occurrence of target
Time: O(log n)
Space: O(1)
Returns: Index of first element > target
"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
# Last occurrence is in right half or at mid
left = mid + 1
else:
# arr[mid] > target
right = mid
return leftJavaScript:
function lowerBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
function upperBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}Java:
public int lowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public int upperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}def binary_search_on_answer(min_answer, max_answer, is_feasible):
"""
For: Optimization problems (minimize maximum, maximize minimum)
Time: O(log(max - min) × feasibility_check_time)
Space: O(1)
Args:
min_answer: Minimum possible answer
max_answer: Maximum possible answer
is_feasible: Function that checks if a candidate answer works
Returns: Optimal answer
"""
left, right = min_answer, max_answer
result = max_answer
while left <= right:
mid = left + (right - left) // 2
if is_feasible(mid):
# mid works, try to find smaller (for minimize maximum)
result = mid
right = mid - 1
else:
# mid doesn't work, need larger value
left = mid + 1
return result
# Example: Koko Eating Bananas
def min_eating_speed(piles, h):
def can_finish(speed):
hours = sum((pile + speed - 1) // speed for pile in piles)
return hours <= h
return binary_search_on_answer(1, max(piles), can_finish)JavaScript:
function binarySearchOnAnswer(minAnswer, maxAnswer, isFeasible) {
let left = minAnswer;
let right = maxAnswer;
let result = maxAnswer;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (isFeasible(mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
// Example: Koko Eating Bananas
function minEatingSpeed(piles, h) {
const canFinish = (speed) => {
const hours = piles.reduce((sum, pile) =>
sum + Math.ceil(pile / speed), 0);
return hours <= h;
};
return binarySearchOnAnswer(1, Math.max(...piles), canFinish);
}Java:
public int binarySearchOnAnswer(int minAnswer, int maxAnswer,
Predicate<Integer> isFeasible) {
int left = minAnswer;
int right = maxAnswer;
int result = maxAnswer;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isFeasible.test(mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}1. Binary Search (LeetCode #704)
def search(nums: List[int], target: int) -> int:
"""
Find target in sorted array
Time: O(log n), Space: O(1)
"""
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
# Example
print(search([1, 3, 5, 7, 9], 7)) # 3
print(search([1, 3, 5, 7, 9], 6)) # -1Why it works: Sorted array allows us to eliminate half the search space with each comparison.
2. Search Insert Position (LeetCode #35)
def searchInsert(nums: List[int], target: int) -> int:
"""
Find index where target should be inserted
Time: O(log n), Space: O(1)
"""
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
# Example
print(searchInsert([1, 3, 5, 7], 4)) # 2 (insert at index 2)
print(searchInsert([1, 3, 5, 7], 0)) # 0 (insert at beginning)Why it works: This is a lower bound search—finding the first position where we could insert the target while maintaining sorted order.
See detailed guide: Find First and Last Position Template
1. Koko Eating Bananas (LeetCode #875)
def minEatingSpeed(piles: List[int], h: int) -> int:
"""
Find minimum eating speed to finish all bananas in h hours
Time: O(n log m) where m = max(piles)
Space: O(1)
"""
def can_finish(speed):
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # Ceiling division
return hours <= h
# Binary search on answer space [1, max(piles)]
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
# Can finish with mid speed, try slower
right = mid
else:
# Too slow, need faster speed
left = mid + 1
return left
# Example
print(minEatingSpeed([3, 6, 7, 11], 8)) # 4
# With speed 4: 1+2+2+3 = 8 hours ✓Why it works: If Koko can finish with speed k, she can finish with any speed > k (monotonic). We binary search for the minimum feasible speed.
2. Capacity To Ship Packages (LeetCode #1011)
def shipWithinDays(weights: List[int], days: int) -> int:
"""
Find minimum ship capacity to ship all packages in given days
Time: O(n log(sum - max))
Space: O(1)
"""
def can_ship(capacity):
days_needed = 1
current_load = 0
for weight in weights:
if current_load + weight > capacity:
days_needed += 1
current_load = weight
else:
current_load += weight
return days_needed <= days
# Answer space: [max(weights), sum(weights)]
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
# Example
print(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 15Why it works: If we can ship with capacity c, we can ship with any capacity > c. Binary search finds the minimum feasible capacity.
See detailed guide: Binary Search on Answer: The Ultimate Guide
1. Search in Rotated Sorted Array (LeetCode #33)
def search(nums: List[int], target: int) -> int:
"""
Search in rotated sorted array
Time: O(log n), Space: O(1)
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (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 < nums[mid]:
# Target is in sorted left half
right = mid - 1
else:
# Target is in unsorted right half
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
# Target is in sorted right half
left = mid + 1
else:
# Target is in unsorted left half
right = mid - 1
return -1
# Example
print(search([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3)) # -1Why it works: In a rotated sorted array, at least one half is always sorted. We identify the sorted half and check if the target is in it.
See detailed guide: Binary Search on Rotated Sorted Arrays
def searchRange(nums: List[int], target: int) -> List[int]:
"""
Find first and last position of target
Time: O(log n), Space: O(1)
"""
def find_first():
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
def find_last():
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 - 1
first = find_first()
if first == len(nums) or nums[first] != target:
return [-1, -1]
last = find_last()
return [first, last]
# Example
print(searchRange([5, 7, 7, 8, 8, 10], 8)) # [3, 4]def searchMatrix(matrix: List[List[int]], target: int) -> bool:
"""
Search in 2D matrix (treat as 1D sorted array)
Time: O(log(m × n)), Space: O(1)
"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
# Convert 1D index to 2D coordinates
row, col = mid // cols, mid % cols
mid_value = matrix[row][col]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return False
# Example
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
print(searchMatrix(matrix, 3)) # Truedef findMin(nums: List[int]) -> int:
"""
Find minimum in rotated sorted array
Time: O(log n), Space: O(1)
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# Minimum is in right half
left = mid + 1
else:
# Minimum is in left half or at mid
right = mid
return nums[left]
# Example
print(findMin([3, 4, 5, 1, 2])) # 1
print(findMin([4, 5, 6, 7, 0, 1, 2])) # 0❌ Wrong:
mid = (left + right) // 2 # Can cause integer overflow in some languages✅ Correct:
mid = left + (right - left) // 2 # Prevents overflowSee guide: Off-by-One Errors in Binary Search
❌ Wrong:
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid # WRONG: can cause infinite loop
else:
right = mid - 1✅ Correct:
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1 # Correct: always make progress
else:
right = midSee guide: Infinite Loop Debugging
❌ Wrong:
# Using <= when you should use <, or vice versa
while left <= right: # For lower bound, should be <
...✅ Correct:
# Classic binary search: left <= right
while left <= right:
...
return -1 # Not found
# Lower/upper bound: left < right
while left < right:
...
return left # Return position❌ Wrong:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
# Crashes if arr is empty!✅ Correct:
def binary_search(arr, target):
if not arr:
return -1
left, right = 0, len(arr) - 1
...See comprehensive guide: Binary Search Implementation Mistakes
Classic Binary Search: O(log n)
Binary Search on Answer: O(log(max - min) × C)
Rotated Array Search: O(log n)
Iterative Implementation: O(1)
Recursive Implementation: O(log n)
Binary search on answer can have higher complexity:
See detailed analysis: When Binary Search Is NOT O(log n)
Q: When should I use binary search vs linear search?
A: Use binary search when:
Use linear search when:
See: Binary Search vs Linear Search
Q: Why does binary search require sorted data?
A: The sorted property allows us to eliminate half the search space with each comparison. Without it, we can't determine which half contains the target.
See: Why Binary Search Requires Sorted Data
Q: How do I avoid infinite loops?
A: Ensure pointer updates always make progress:
left <= right, use left = mid + 1 and right = mid - 1left < right, use left = mid + 1 and right = mid (or vice versa)Q: What's the difference between lower bound and upper bound?
A:
See: Find First and Last Position Template
Q: How do I recognize binary search on answer problems?
A: Look for:
See: Binary Search on Answer Guide
Binary search is a fundamental algorithm that every software engineer must master. It's not just about finding elements in sorted arrays—it's a powerful problem-solving paradigm that applies to optimization problems, rotated structures, and implicit search spaces.
Key principles:
The decision framework:
Master these templates:
while left <= right with left = mid + 1 and right = mid - 1while left < right with careful pointer updatesPractice the roadmap, understand the intuition, and you'll recognize binary search opportunities instantly. For specific patterns, explore Binary Search on Answer, Rotated Arrays, and Implementation Mistakes.
Next time you see a sorted array or a "minimize maximum" problem, reach for binary search.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free