A
AiTechWorlds
AiTechWorlds
You're on a game show. The host says: "There's a prize worth between $1 and $1,000. Guess the price. I'll tell you higher or lower after each guess."
What do you do? You don't start at $1 and count up. You guess $500. "Higher." You guess $750. "Lower." You guess $625. "Higher." You guess $687. "Lower."
Within ten guesses, you've pinpointed the exact price. You've just run binary search — without even thinking about it.
This is the key insight: Binary search isn't just for finding values in arrays. It's a way of thinking about any problem where you can eliminate half the possibilities with a single test.
The template for any binary search problem is:
1. Define a search space [left, right]
2. Define a condition: does this value satisfy the requirement?
3. Narrow the space: if condition met → search left half (or right half)
4. Repeat until the space collapses to a single answer
Once you see this pattern, you'll find binary search hiding inside dozens of problem types.
Problem: In a sorted array with duplicates, find the first index where the target appears.
def find_first(arr, target):
left, right = 0, len(arr) - 1
result = -1 # Track best (leftmost) match found so far
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid # Record this match
right = mid - 1 # Keep searching LEFT for an earlier match
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# --- Example ---
arr = [2, 4, 4, 4, 7, 9, 9, 11]
print(find_first(arr, 4)) # Output: 1 (first 4 is at index 1)
print(find_first(arr, 9)) # Output: 5 (first 9 is at index 5)
Output:
1
5
Problem: Find the last index where target appears.
def find_last(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid # Record this match
left = mid + 1 # Keep searching RIGHT for a later match
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
# --- Example ---
arr = [2, 4, 4, 4, 7, 9, 9, 11]
print(find_last(arr, 4)) # Output: 3 (last 4 is at index 3)
print(find_last(arr, 9)) # Output: 6 (last 9 is at index 6)
Output:
3
6
Problem: Find where a value would be inserted to keep the array sorted.
Python's built-in bisect module handles this perfectly:
import bisect
# bisect_left: find leftmost position to insert target
# bisect_right: find rightmost position to insert target
arr = [10, 20, 30, 40, 50]
print(bisect.bisect_left(arr, 30)) # Output: 2 (before existing 30)
print(bisect.bisect_right(arr, 30)) # Output: 3 (after existing 30)
print(bisect.bisect_left(arr, 25)) # Output: 2 (between 20 and 30)
Output:
2
3
2
import bisect
scores = [10, 20, 30, 40, 50, 60, 70, 80, 90]
grade_boundaries = [60, 70, 80, 90, 100]
grades = ['F', 'D', 'C', 'B', 'A']
def get_grade(score):
# bisect_left finds where score fits in grade_boundaries
# That index maps directly to the grades list
return grades[bisect.bisect_left(grade_boundaries, score)]
for score in [55, 65, 75, 85, 95]:
print(f"Score {score}: {get_grade(score)}")
Output:
Score 55: F
Score 65: D
Score 75: C
Score 85: B
Score 95: A
How it works: bisect_left(grade_boundaries, 65) finds that 65 belongs at index 1 (after 60, before 70) — which maps to grades[1] = 'D'. No if-elif chains needed.
Problem: A sorted array has been rotated at some pivot. Example: [4, 5, 6, 7, 0, 1, 2] (rotated from [0, 1, 2, 4, 5, 6, 7]). Find the target.
Original: [0, 1, 2, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 0, 1, 2]
^--- rotation point
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# Determine which half is sorted
if arr[left] <= arr[mid]: # LEFT half is sorted
if arr[left] <= target < arr[mid]: # Target is in left half
right = mid - 1
else: # Target is in right half
left = mid + 1
else: # RIGHT half is sorted
if arr[mid] < target <= arr[right]: # Target is in right half
left = mid + 1
else: # Target is in left half
right = mid - 1
return -1
# --- Example ---
arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0)) # Output: 4
print(search_rotated(arr, 3)) # Output: -1
Output:
4
-1
Problem: A peak element is one that is greater than its neighbors. Find any peak.
def find_peak(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] > arr[mid + 1]: # Descending — peak is in LEFT half
right = mid # (mid itself could be the peak)
else: # Ascending — peak is in RIGHT half
left = mid + 1
return left # left == right, this is the peak index
# --- Example ---
arr = [1, 3, 20, 4, 1, 0]
peak_idx = find_peak(arr)
print(f"Peak is {arr[peak_idx]} at index {peak_idx}") # Output: Peak is 20 at index 2
Output:
Peak is 20 at index 2
This is the most powerful application. Instead of searching an array, you search the space of possible answers.
Pattern: "Find the minimum value of X such that condition(X) is true."
Example Problem: What is the minimum number of days needed to ship all packages if you can carry at most capacity weight per day?
def can_ship(weights, capacity, days):
"""Check if all packages can be shipped in `days` days with given capacity."""
current_load = 0
days_used = 1
for w in weights:
if current_load + w > capacity:
days_used += 1
current_load = 0
current_load += w
return days_used <= days
def min_ship_capacity(weights, days):
left = max(weights) # Minimum: must fit heaviest package
right = sum(weights) # Maximum: ship everything in one day
while left < right:
mid = left + (right - left) // 2
if can_ship(weights, mid, days):
right = mid # mid works — try smaller
else:
left = mid + 1 # mid too small — try larger
return left
# --- Example ---
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(min_ship_capacity(weights, 5)) # Output: 15
Output:
15
The answer space is [10, 55]. We binary search over possible capacities, checking if each one allows shipping in 5 days.
def binary_search_template(search_space_start, search_space_end, condition):
"""
Find the minimum value in [start, end] where condition(value) is True.
Assumes: condition is False for small values, True for large values.
"""
left, right = search_space_start, search_space_end
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid # mid satisfies condition — try smaller
else:
left = mid + 1 # mid doesn't satisfy — go larger
return left # Smallest value satisfying condition
| Variation | Key Modification | Use When |
|---|---|---|
| Standard search | Return on match | Find any occurrence |
| First occurrence | On match, save & go left | Find leftmost duplicate |
| Last occurrence | On match, save & go right | Find rightmost duplicate |
| Insertion point | bisect_left / bisect_right | Maintain sorted order |
| Rotated array | Check which half is sorted | Rotated sorted array |
| Peak finding | Compare mid vs mid+1 | Find local maximum |
| Answer space | Search over possible values | Optimization with monotonic condition |
Binary search on answer space problems are among the most highly-rated interview questions at top tech companies. They test whether you can recognize the abstract structure of a problem rather than just apply memorized algorithms.
Whenever you see: "find minimum X such that..." or "what is the smallest/largest value that satisfies...", think binary search on the answer space.
Common interview problems in this category:
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises