Practice Session 3: Binary Search
Problem 1: Find Peak Element
Link: LeetCode 162
Quick Summary: Find any peak element where nums[i] > nums[i-1] and nums[i] > nums[i+1].
Industry Context: Finding local maxima in metrics (CPU spikes, traffic peaks), anomaly detection
Solutions
Approach 1: Linear Scan
public int findPeakElement(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return i;
}
}
return nums.length - 1;
}- Time: O(n)
- Space: O(1)
- Tradeoff: Works but doesn’t use “any peak is valid” property
Approach 2: Binary Search (Optimal)
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
// Peak is on left side (or mid is peak)
right = mid;
} else {
// Peak is on right side
left = mid + 1;
}
}
return left;
}- Time: O(log n)
- Space: O(1)
- Key Insight: Always move toward higher value, guaranteed to find a peak
Problem 2: Search in 2D Matrix II
Link: LeetCode 240
Quick Summary: Search in matrix with sorted rows and sorted columns.
Industry Context: Database indexing (composite indexes), spatial data structures
Solutions
Approach 1: Binary Search Each Row
public boolean searchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
if (binarySearch(row, target)) {
return true;
}
}
return false;
}
private boolean binarySearch(int[] row, int target) {
int left = 0, right = row.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (row[mid] == target) return true;
else if (row[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}- Time: O(m log n) - m rows, n columns
- Space: O(1)
- Tradeoff: Doesn’t fully utilize column sorting
Approach 2: Start from Top-Right (Optimal)
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--; // Move left
} else {
row++; // Move down
}
}
return false;
}- Time: O(m + n)
- Space: O(1)
- Key Insight: Top-right position allows elimination of row OR column each step
- Tradeoff: Not traditional binary search, but most efficient
Problem 3: Koko Eating Bananas
Link: LeetCode 875
Quick Summary: Find minimum eating speed k to finish all bananas within h hours.
Industry Context: Rate limiting, capacity planning, resource throttling
Solution: Binary Search on Answer
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
// Find max pile (upper bound)
for (int pile : piles) {
right = Math.max(right, pile);
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, h, mid)) {
right = mid; // Try slower speed
} else {
left = mid + 1; // Need faster speed
}
}
return left;
}
private boolean canFinish(int[] piles, int h, int speed) {
long hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed; // Ceiling division
}
return hours <= h;
}- Time: O(n log m) - n piles, m = max pile size
- Space: O(1)
- Pattern: “Minimize maximum” or “maximize minimum” → binary search on answer
- Gotcha: Use ceiling division, watch for integer overflow
Problem 4: Capacity To Ship Packages Within D Days
Link: LeetCode 1011
Quick Summary: Find minimum ship capacity to ship all packages within D days.
Industry Context: Logistics optimization, network bandwidth allocation, batch processing
Solution: Binary Search on Capacity
public int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
for (int weight : weights) {
left = Math.max(left, weight); // Min capacity = largest package
right += weight; // Max capacity = sum of all
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) {
right = mid; // Try smaller capacity
} else {
left = mid + 1; // Need larger capacity
}
}
return left;
}
private boolean canShip(int[] weights, int days, int capacity) {
int daysNeeded = 1;
int currentLoad = 0;
for (int weight : weights) {
if (currentLoad + weight > capacity) {
daysNeeded++;
currentLoad = weight;
if (daysNeeded > days) return false;
} else {
currentLoad += weight;
}
}
return true;
}- Time: O(n log S) - n packages, S = sum of weights
- Space: O(1)
- Same Pattern: Split Array Largest Sum, Allocate Mailboxes
Problem 5: Time-Based Key-Value Store
Link: LeetCode 981
Quick Summary: Store key-value pairs with timestamp, retrieve value at or before given timestamp.
Industry Context: Version control systems, time-series databases, event sourcing
Solution: HashMap + Binary Search
class TimeMap {
private Map<String, List<Pair>> map;
static class Pair {
int timestamp;
String value;
Pair(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
}
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
map.computeIfAbsent(key, k -> new ArrayList<>())
.add(new Pair(timestamp, value));
}
public String get(String key, int timestamp) {
if (!map.containsKey(key)) return "";
List<Pair> pairs = map.get(key);
return binarySearch(pairs, timestamp);
}
private String binarySearch(List<Pair> pairs, int timestamp) {
int left = 0, right = pairs.size() - 1;
String result = "";
while (left <= right) {
int mid = left + (right - left) / 2;
if (pairs.get(mid).timestamp <= timestamp) {
result = pairs.get(mid).value;
left = mid + 1; // Look for later timestamp
} else {
right = mid - 1;
}
}
return result;
}
}- Time: O(1) set, O(log n) get where n = versions per key
- Space: O(n) total key-value pairs
- Pattern: Binary search for “rightmost valid” value
Java 21+ Features in Binary Search
Pattern Matching for Type-Safe Bounds
// Java 21+
public int binarySearch(Object[] arr, int target) {
return switch (arr) {
case Integer[] nums -> searchIntegers(nums, target);
case String[] strs -> searchStrings(strs, String.valueOf(target));
default -> -1;
};
}Record Patterns for Cleaner Code
// Java 21+
record Range(int start, int end) {}
public boolean isInRange(Range range, int value) {
return switch (range) {
case Range(int s, int e) when value >= s && value <= e -> true;
default -> false;
};
}Key Takeaways
Binary Search Templates
1. Find Exact Value
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;
}2. Find Left Boundary (First Occurrence)
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) right = mid;
else left = mid + 1;
}3. Find Right Boundary (Last Occurrence)
while (left < right) {
int mid = left + (right - left) / 2 + 1; // Round up!
if (arr[mid] <= target) left = mid;
else right = mid - 1;
}4. Binary Search on Answer
while (left < right) {
int mid = left + (right - left) / 2;
if (isValid(mid)) {
right = mid; // For minimization
// left = mid + 1; // For maximization
} else {
left = mid + 1; // For minimization
// right = mid; // For maximization
}
}When to Use Binary Search
- ✅ Sorted/monotonic data
- ✅ “Can we achieve X?” → search for optimal X
- ✅ Finding boundaries/thresholds
- ❌ Unsorted data (unless you can sort)
- ❌ Need all solutions (binary search finds one)
Common Pitfalls
- Overflow: Use
left + (right - left) / 2not(left + right) / 2 - Infinite Loop: Check rounding direction for right boundary search
- Off-by-one:
left <= rightvsleft < rightdepends on template - Validation Function: Ensure monotonicity in binary search on answer