- Solve complex problems combining multiple binary search concepts
- Master median finding in sorted arrays
- Apply binary search to matrix and array partitioning problems
- Develop pattern recognition for binary search opportunities
Advanced Binary Search Problems
At this point, you understand binary search deeply. You know how to search sorted arrays, handle duplicates, work with rotated arrays, and even search on answer spaces. Now let's tackle some problems that combine these concepts in interesting ways.
These are the kinds of problems you'll see in technical interviews at top companies. They're not harder because the binary search itself is complex—they're harder because recognizing that binary search applies takes insight.
Problem: Median of Two Sorted Arrays
You have two sorted arrays and need to find the median of their combined elements. The naive approach: merge them (O(m+n)) and find the middle. But we can do O(log(min(m, n))) with binary search.
The key insight: the median divides elements into two halves. If we partition each array at the right points, the left halves contain the smaller elements and the right halves contain the larger elements.
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the smaller array
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
partition1 = (left + right) // 2
partition2 = (m + n + 1) // 2 - partition1
# Get boundary values
max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
min_right1 = float('inf') if partition1 == m else nums1[partition1]
max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
min_right2 = float('inf') if partition2 == n else nums2[partition2]
# Check if we found the right partition
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Perfect partition found
if (m + n) % 2 == 0:
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
else:
return max(max_left1, max_left2)
elif max_left1 > min_right2:
# nums1 partition is too far right
right = partition1 - 1
else:
# nums1 partition is too far left
left = partition1 + 1
raise ValueError("Input arrays are not sorted")
We're binary searching the partition point in the smaller array. Each partition in array 1 determines the partition in array 2 (since we know how many elements should be on the left). We check if the partitions are valid by ensuring the max of left halves is less than the min of right halves.
This is a hard problem, and it shows how binary search can solve problems that don't look like searching at all.
Problem: Kth Smallest Element in a Sorted Matrix
You have an n×n matrix where each row and column is sorted. Find the kth smallest element.
You might think of heaps or sorting, but there's a binary search solution: search the answer space.
def kth_smallest(matrix, k):
n = len(matrix)
left, right = matrix[0][0], matrix[n-1][n-1]
def count_less_equal(mid):
# Count elements <= mid
count = 0
col = n - 1
for row in range(n):
# For each row, find how many elements <= mid
while col >= 0 and matrix[row][col] > mid:
col -= 1
count += col + 1
return count
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left
We binary search on the value range. For each candidate value mid, we count how many elements in the matrix are less than or equal to mid. If that count is less than k, the kth element must be larger. Otherwise, it's less than or equal to mid.
The counting is clever: start at the top-right and work down and left, using the sorted property to count efficiently in O(n) time.
Problem: Minimum in Rotated Sorted Array
Finding an element in a rotated array is one thing. Finding the minimum is another angle on the same problem.
def find_min_rotated(arr):
left, right = 0, len(arr) - 1
# If array wasn't rotated
if arr[left] < arr[right]:
return arr[left]
while left < right:
mid = (left + right) // 2
# Check if mid is the minimum
if arr[mid] > arr[mid + 1]:
return arr[mid + 1]
if arr[mid - 1] > arr[mid]:
return arr[mid]
# Determine which half is unsorted (contains the min)
if arr[mid] > arr[right]:
# Min is in right half
left = mid + 1
else:
# Min is in left half
right = mid
return arr[left]
The minimum is at the "rotation point" where the order breaks. We binary search to find that point by checking which half is out of order.
Problem: Split Array Largest Sum
You have an array and must split it into k subarrays to minimize the largest sum among those subarrays. This is binary search on the answer.
def split_array(nums, k):
def can_split(max_sum):
# Can we split into k subarrays with each sum <= max_sum?
subarrays = 1
current_sum = 0
for num in nums:
if num > max_sum:
return False
if current_sum + num > max_sum:
subarrays += 1
current_sum = num
if subarrays > k:
return False
else:
current_sum += num
return True
left, right = max(nums), sum(nums)
while left < right:
mid = (left + right) // 2
if can_split(mid):
right = mid # This max works, try smaller
else:
left = mid + 1 # Too small
return left
The answer must be between max(nums) (one subarray per element) and sum(nums) (one subarray total). We binary search this range, testing each candidate max_sum to see if we can split the array accordingly.
Problem: Capacity to Ship Packages
You're shipping packages and need to ship them all within D days. What's the minimum ship capacity needed?
def ship_within_days(weights, D):
def can_ship(capacity):
days = 1
current_weight = 0
for weight in weights:
if weight > capacity:
return False
if current_weight + weight > capacity:
days += 1
current_weight = weight
if days > D:
return False
else:
current_weight += weight
return True
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
Notice the pattern similarity to previous problems? Minimum capacity is max(weights), maximum is sum(weights), and we binary search that range.
Problem: Find Smallest Letter Greater Than Target
Given a sorted list of letters and a target letter, find the smallest letter greater than target.
def next_greatest_letter(letters, target):
left, right = 0, len(letters)
while left < right:
mid = (left + right) // 2
if letters[mid] <= target:
left = mid + 1
else:
right = mid
# Wrap around if necessary
return letters[left % len(letters)]
This is essentially finding the upper bound, with a twist for wrap-around. It shows how versatile the binary search template is.
The Common Thread
All these problems share key characteristics:
- A search space (array indices, value ranges, capacities, etc.)
- Monotonicity (if X works, all X+1, X+2... work, or vice versa)
- A validation function (can I do X with capacity Y?)
When you see these three things, think binary search.
Problem-Solving Strategy
When faced with a potential binary search problem:
- Identify what you're searching for (an index? a value? an answer?)
- Define the search space (what are the min and max possibilities?)
- Check for monotonicity (if X works, what about X+1?)
- Write the validation function (how do I test if candidate X works?)
- Apply binary search template (adjust boundaries based on validation)
Real Interview Advice
These problems appear in interviews because they test multiple skills:
- Algorithm knowledge (binary search)
- Problem recognition (seeing when binary search applies)
- Coding accuracy (off-by-one errors are common)
- Complexity analysis (understanding O(log n) advantage)
When you're stuck on a "find minimum X such that Y" or "find maximum X such that Y" problem, always ask: can I binary search this?
Practice Problems
- Find Peak Element II (2D version)
- Koko Eating Bananas (classic binary search on answer)
- Magnetic Force Between Two Balls (positioning problem)
- Minimize Max Distance to Gas Station (resource allocation)
- Find K Closest Elements (combining binary search with other techniques)
The more you practice, the better you'll get at recognizing the patterns. Eventually, you'll see binary search opportunities everywhere—and that's when you've truly mastered it.