🔍 Binary Search Patterns: The Ultimate Treasure Hunt
Imagine you’re looking for a hidden treasure in a row of 1000 numbered boxes. Would you open them one by one? Or would you be clever about it?
🎯 The Big Idea: Divide and Conquer
Binary Search is like playing a guessing game. Your friend thinks of a number between 1 and 100. Each time you guess, they say “higher” or “lower.”
The smart move? Always guess the middle. This cuts your possibilities in half every single time!
100 boxes → 50 → 25 → 12 → 6 → 3 → 1
Only 7 guesses to find anything!
📚 1. Binary Search Fundamentals
The Core Recipe
Think of a sorted bookshelf. To find book #47:
- Look at the middle book
- If it’s #47 → Found it! 🎉
- If #47 is smaller → look in the left half
- If #47 is bigger → look in the right half
- Repeat until found
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
Example: Finding 7
Array: [1, 3, 5, 7, 9, 11, 13]
Step 1: mid = 7 (index 3) → Found! 🎉
Time Complexity: O(log n) — Lightning fast!
📚 2. Binary Search Variants
🔹 Find First Occurrence
When duplicates exist, find the leftmost match.
Like finding the first person named “Alex” in a sorted attendance list.
def first_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Keep looking left
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
🔹 Find Last Occurrence
Find the rightmost match instead.
def last_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # Keep looking right
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
Example
Array: [1, 2, 2, 2, 3, 4]
Target: 2
First occurrence: index 1
Last occurrence: index 3
📚 3. Search in Rotated Sorted Array
The Twist
Imagine a sorted array that got rotated — like spinning a deck of cards and cutting it mid-way.
Original: [1, 2, 3, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 1, 2, 3]
↑ starts here now!
The Trick
At least one half is always sorted! Check which half is sorted, then decide where to look.
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
# Left half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
Example
Array: [4, 5, 6, 7, 0, 1, 2]
Find: 0
mid = 7 → Right half has 0
mid = 1 → Left half has 0
Found at index 4! 🎉
📚 4. Find Minimum in Rotated Sorted Array
The Challenge
Find the smallest element in a rotated array — it’s the pivot point!
[4, 5, 6, 7, 0, 1, 2]
↑ minimum!
The Pattern
The minimum is where the rotation happened. Look for where the order “breaks.”
def find_min(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > arr[right]:
# Min is in right half
left = mid + 1
else:
# Min is in left half (including mid)
right = mid
return arr[left]
Example
Array: [3, 4, 5, 1, 2]
mid = 5 → 5 > 2 → go right
mid = 1 → 1 < 2 → go left
Answer: 1 🎉
📚 5. Find Peak Element
What’s a Peak?
A peak is an element greater than its neighbors.
[1, 3, 7, 4, 2]
↑ peak!
The Insight
If you’re going uphill, a peak is ahead. If you’re going downhill, a peak is behind.
def find_peak(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] < arr[mid + 1]:
# Going uphill, peak is ahead
left = mid + 1
else:
# Going downhill, peak is here or behind
right = mid
return left # Index of peak
Example
Array: [1, 2, 1, 3, 5, 6, 4]
mid = 3 → 3 < 5 → go right
mid = 6 → 6 > 4 → go left
Peak at index 5 (value 6) 🎉
📚 6. Binary Search on Answer
The Big Shift
Instead of searching in an array, we search for the best answer in a range of possibilities.
Think: “What’s the minimum capacity needed to ship packages in 5 days?”
The Pattern
1. Define possible answer range [min, max]
2. Check if mid value works (feasibility check)
3. If yes → try smaller (minimize) or larger (maximize)
4. If no → adjust range accordingly
Example: Square Root
Find √16 without using math.sqrt()
def sqrt(n):
left, right = 0, n
answer = 0
while left <= right:
mid = (left + right) // 2
if mid * mid <= n:
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
# sqrt(16) = 4 🎉
📚 7. Capacity to Ship Packages Pattern
The Problem
Ship packages within D days. Each package has a weight. Find the minimum ship capacity needed.
Packages: [1, 2, 3, 4, 5]
Days: 3
The Approach
- Min capacity = largest package (must fit!)
- Max capacity = sum of all packages (ship all in 1 day)
- Binary search for the minimum valid capacity
def ship_packages(weights, days):
def can_ship(capacity):
day_count = 1
current_load = 0
for w in weights:
if current_load + w > capacity:
day_count += 1
current_load = 0
current_load += w
return day_count <= days
left = max(weights)
right = sum(weights)
while left < right:
mid = (left + right) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
Example
Packages: [1, 2, 3, 4, 5], Days: 3
Capacity 6: Day1:[1,2,3] Day2:[4] Day3:[5] → 3 days ✓
Capacity 5: Day1:[1,2] Day2:[3] Day3:[4] Day4:[5] → 4 days ✗
Answer: 6 🎉
📚 8. Split Array Largest Sum
The Problem
Split an array into M parts. Minimize the largest sum among all parts.
Array: [7, 2, 5, 10, 8]
M: 2
Split: [7, 2, 5] and [10, 8]
Sums: 14 and 18
Largest: 18
The Insight
This is the inverse of the shipping problem! We’re limiting the “load” (sum) per “ship” (subarray).
def split_array(nums, m):
def can_split(max_sum):
parts = 1
current_sum = 0
for n in nums:
if current_sum + n > max_sum:
parts += 1
current_sum = 0
current_sum += n
return parts <= m
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2
if can_split(mid):
right = mid
else:
left = mid + 1
return left
Example
Array: [7, 2, 5, 10, 8], M: 2
max_sum = 18: [7,2,5] [10,8] → 2 parts ✓
max_sum = 17: [7,2,5] [10] [8] → 3 parts ✗
Answer: 18 🎉
🗺️ The Pattern Map
graph TD A["Binary Search Problem"] --> B{Sorted Array?} B -->|Yes| C{Normal or Rotated?} B -->|No - Search Answer Range| D["Binary Search on Answer"] C -->|Normal| E["Standard Binary Search"] C -->|Rotated| F{Find What?} F -->|Target Value| G["Search in Rotated Array"] F -->|Minimum Element| H["Find Minimum in Rotated"] E --> I{Duplicates?} I -->|Yes| J["First/Last Occurrence Variant"] I -->|No| K["Classic Binary Search"] D --> L["Capacity/Split Problems"] D --> M["Find Peak Element"]
🎁 Key Takeaways
| Pattern | When to Use | Key Insight |
|---|---|---|
| Basic BS | Sorted array, find target | Halve the search space |
| Variants | Find first/last occurrence | Continue after finding |
| Rotated | Shifted sorted array | One half is always sorted |
| Find Min | Rotated array, find pivot | Look for the “break” |
| Peak | Find local maximum | Follow the uphill direction |
| BS on Answer | Optimize min/max result | Search possible answers |
| Capacity | Distribute within limit | Binary search on capacity |
| Split Sum | Minimize maximum chunk | Same as capacity pattern! |
🚀 You’ve Got This!
Binary search isn’t just about finding elements — it’s a thinking pattern. Whenever you see:
- Sorted data
- Min/max optimization
- “Is this value possible?”
Think Binary Search!
Keep practicing, keep halving, keep conquering! 🏆