Binary Search Patterns: The Art of Finding Things Fast 🔍
The Story of the Magic Guessing Game
Imagine you’re playing a game with your friend. They pick a number between 1 and 100, and you have to guess it. After each guess, they say “higher” or “lower.”
The silly way: Guess 1, then 2, then 3… (could take 100 guesses!)
The smart way: Guess 50 first. If “higher,” you now only need to search 51-100. If “lower,” search 1-49. You just cut your work in HALF with one guess!
This is Binary Search - the magic trick of cutting your problem in half, again and again, until you find your answer.
🎯 Binary Search Fundamentals
The Core Idea
Binary Search is like playing the “higher/lower” guessing game. You:
- Look at the middle
- Decide which half to keep
- Throw away the other half
- Repeat until found!
The Rules
- Your list MUST be sorted (like numbers in order: 1, 3, 5, 7, 9)
- Each step removes half the remaining items
- Finding something in 1 million items takes only ~20 guesses!
The Code Pattern
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; // Found it!
} else if (arr[mid] < target) {
left = mid + 1; // Go right
} else {
right = mid - 1; // Go left
}
}
return -1; // Not found
}
Why left + (right - left) / 2?
This prevents integer overflow! If left and right are both huge numbers, adding them might break. This formula is safe.
🔀 Binary Search Variants
Not all searches are the same! Sometimes you need special versions:
1. Find First Occurrence
When duplicates exist, find the leftmost one:
int findFirst(int[] arr, int target) {
int left = 0, right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid; // Save it
right = mid - 1; // Keep looking left
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
2. Find Last Occurrence
Find the rightmost occurrence:
int findLast(int[] arr, int target) {
int left = 0, right = arr.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid; // Save it
left = mid + 1; // Keep looking right
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
3. Lower Bound & Upper Bound
- Lower Bound: First position where value >= target
- Upper Bound: First position where value > target
These are super useful for “find where this would fit” questions!
🌀 Search in Rotated Sorted Array
The Story
Imagine a sorted bookshelf that someone rotated - they took some books from the left and moved them to the right.
Original: [1, 2, 3, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 1, 2, 3]
(books 4-7 moved to front)
It’s like a clock that got shifted - still ordered, but the start moved!
The Trick
One half is always sorted. Find which half, then decide where your target could be:
int searchRotated(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
// Left half is sorted?
if (arr[left] <= arr[mid]) {
// Target in left half?
if (target >= arr[left] &&
target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
// Target in right half?
if (target > arr[mid] &&
target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
Visual Flow
graph TD A["Find Mid"] --> B{arr left less than or equal to arr mid?} B -->|Yes| C["Left half sorted"] B -->|No| D["Right half sorted"] C --> E{Target in left half?} D --> F{Target in right half?} E -->|Yes| G["Search Left"] E -->|No| H["Search Right"] F -->|Yes| I["Search Right"] F -->|No| J["Search Left"]
📉 Find Minimum in Rotated Sorted Array
The Goal
Find the smallest element (the rotation point).
The Insight
The minimum is where the array “breaks” - where a bigger number is followed by a smaller one.
int findMin(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// Mid is bigger than right?
// Min must be in right half!
if (arr[mid] > arr[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return arr[left];
}
Example Walkthrough
Array: [4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
mid = 3 → arr[3] = 7
7 > 2? YES → min is right side
left = 4
mid = 5 → arr[5] = 1
1 > 2? NO → min could be here
right = 5
left == right → Found! arr[4] = 0
🏔️ Find Peak Element
The Story
Imagine a mountain range. A peak is any point higher than its neighbors. We need to find ANY peak (not necessarily the highest).
The Magic
If you’re going uphill, there MUST be a peak ahead. If going downhill, there’s a peak behind!
int findPeak(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// Going uphill? Peak is ahead
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
}
// Going downhill? Peak is here/behind
else {
right = mid;
}
}
return left; // Peak position
}
Visual
Peak here! (or higher)
↓
▲ ▲▲▲
▲▲▲ ▲ ▲
â–˛ â–˛ â–˛
â–˛ â–˛
If mid is going UP (arr[mid] < arr[mid+1]), the peak is on the RIGHT.
If mid is going DOWN, the peak is on the LEFT (or at mid).
🎯 Binary Search on Answer
A New Way to Think
Sometimes you don’t search IN an array. Instead, you search for the best answer to a question!
The Pattern:
- Define a range of possible answers (min to max)
- For each potential answer, check: “Is this valid?”
- Binary search to find the optimal one!
Example: Square Root
Find the square root of 16:
- Possible answers: 0 to 16
- Check mid=8: 8×8=64 > 16 → too big
- Check mid=4: 4×4=16 = 16 → perfect!
int sqrt(int n) {
int left = 0, right = n;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long)mid * mid <= n) {
result = mid; // Possible answer
left = mid + 1; // Try bigger
} else {
right = mid - 1; // Too big
}
}
return result;
}
📦 Capacity To Ship Packages Pattern
The Story
You’re a ship captain. You have packages with different weights. You must deliver ALL packages in D days. What’s the minimum ship capacity you need?
The Rules
- Packages must stay in order (no rearranging)
- Each day, load packages until you can’t fit more
- Find the smallest ship that works!
The Approach
- Minimum capacity: heaviest single package (must fit!)
- Maximum capacity: total weight of all packages (ship everything in 1 day)
- Binary search between these to find optimal!
int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
// Set search range
for (int w : weights) {
left = Math.max(left, w); // Min = heaviest
right += w; // Max = total
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid; // Try smaller
} else {
left = mid + 1; // Need bigger
}
}
return left;
}
boolean canShip(int[] w, int days, int cap) {
int count = 1, load = 0;
for (int pkg : w) {
if (load + pkg > cap) {
count++; // New day
load = pkg;
} else {
load += pkg;
}
}
return count <= days;
}
Example
Packages: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Days: 5
Min capacity = 10 (heaviest package)
Max capacity = 55 (total weight)
Binary search finds: capacity = 15
Day 1: [1,2,3,4,5] = 15
Day 2: [6,7] = 13
Day 3: [8] = 8
Day 4: [9] = 9
Day 5: [10] = 10
🔢 Split Array Largest Sum
The Story
You have an array and must split it into M parts. Each part has a sum. You want the biggest sum to be as small as possible.
It’s like splitting chores among friends - you want the busiest person to have as little work as possible!
Same Pattern!
This is the SAME as ship capacity:
- “Capacity” = maximum sum allowed per part
- “Days” = number of splits (M)
- Find the minimum “capacity” that works!
int splitArray(int[] nums, int m) {
int left = 0, right = 0;
for (int n : nums) {
left = Math.max(left, n); // Min = largest element
right += n; // Max = total sum
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, m, mid)) {
right = mid; // Try smaller max
} else {
left = mid + 1; // Need larger max
}
}
return left;
}
boolean canSplit(int[] nums, int m, int maxSum) {
int parts = 1, currSum = 0;
for (int n : nums) {
if (currSum + n > maxSum) {
parts++;
currSum = n;
} else {
currSum += n;
}
}
return parts <= m;
}
Example
Array: [7, 2, 5, 10, 8]
Split into: 2 parts
Min max-sum = 10 (largest element)
Max max-sum = 32 (total)
Binary search finds: 18
Split 1: [7, 2, 5] = 14
Split 2: [10, 8] = 18
Maximum sum is 18 (minimum possible!)
🗺️ The Complete Pattern Map
graph LR A["Binary Search Patterns"] --> B["Basic Search"] A --> C["Search on Answer"] B --> D["Standard BS"] B --> E["Variants"] B --> F["Modified Arrays"] E --> E1["First Occurrence"] E --> E2["Last Occurrence"] E --> E3["Lower/Upper Bound"] F --> F1["Rotated Search"] F --> F2["Find Minimum"] F --> F3["Find Peak"] C --> G["Ship Packages"] C --> H["Split Array"] C --> I["Square Root/Nth Root"]
🎓 Key Takeaways
-
Binary Search = Cut in Half - Every step eliminates half the possibilities
-
Sorted is Required - For basic BS, array must be sorted
-
Rotated Arrays - One half is always sorted; use that!
-
Peak Finding - Follow the uphill direction
-
Binary Search on Answer - When you’re not searching IN data, but FOR the optimal answer
-
Capacity Pattern - Works for shipping, splitting, and many “minimize the maximum” problems
🚀 You’ve Got This!
Binary Search is like having a superpower. While others check one item at a time, you zoom to the answer by being clever about what to throw away.
Remember:
- Always ask: Can I cut this problem in half?
- Check: Is the data sorted (or rotated sorted)?
- Think: Am I searching IN data or FOR an answer?
Now go find things FAST! 🎯