Binary search isn't just for sorted arrays — it applies to any monotonic function. 'Binary search on the answer' is a powerful technique for optimization problems.
Problems: 7
Easy: 1
Medium: 5
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Given m×n matrix where rows are sorted and the first integer of each row is greater than the last of the previous row, search for a target value. Must run in O(log(m×n)).
binary search on answerceil divisionmonotonic feasibility
Is there a monotonic relationship between speed k and feasibility? If k works, does k+1 also work?
Python Solution
import math
def minEatingSpeed(piles, h):
left, right = 1, max(piles)
while left < right:
mid = (left + right) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
right = mid # mid is feasible, try lower
else:
left = mid + 1 # too slow, need faster
return left
Key idea: Binary search on the answer (speed k). The feasibility function is monotonic: if k works, anything larger also works. Find the smallest feasible k.
rotated array logicnums[mid] vs nums[right]O(log n)
Compare mid to the right boundary. If mid > right, the minimum is in the right half. Otherwise it's in the left half (including mid).
Python Solution
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1 # min is in the right portion
else:
right = mid # min is in the left portion (mid could be min)
return nums[left]
Key idea: Compare mid to the rightmost element. If mid > right, the array is not sorted in [mid, right] — min must be to the right of mid. Otherwise, min is in [left, mid].
Design a data structure that stores key-value pairs with timestamps. set(key, value, timestamp) stores the value; get(key, timestamp) returns the value with the largest timestamp ≤ given timestamp.
defaultdict of listbisect_rightbinary search on timestamps
Store (timestamp, value) pairs sorted by timestamp. For get, binary search for the largest timestamp ≤ given.
Python Solution
from collections import defaultdict
import bisect
class TimeMap:
def __init__(self):
self.store = defaultdict(list) # key → [(timestamp, value)]
def set(self, key, value, timestamp):
self.store[key].append((timestamp, value))
def get(self, key, timestamp):
if key not in self.store:
return ""
pairs = self.store[key]
# Find rightmost timestamp <= given timestamp
idx = bisect.bisect_right(pairs, (timestamp, chr(127))) - 1
return pairs[idx][1] if idx >= 0 else ""
Key idea:set appends in order (timestamps are strictly increasing). get uses binary search to find the largest stored timestamp ≤ query. bisect_right finds the insertion point just past the target.
binary search on partitionensure nums1 shorterO(log min(m,n))
Binary search on the partition of nums1. For the partition to be correct, the max of the left sides must be ≤ min of the right sides.
Python Solution
def findMedianSortedArrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n) // 2
left, right = 0, m
while True:
i = (left + right) // 2 # partition index for nums1
j = half - i # partition index for nums2
l1 = nums1[i-1] if i > 0 else float('-inf')
r1 = nums1[i] if i < m else float('inf')
l2 = nums2[j-1] if j > 0 else float('-inf')
r2 = nums2[j] if j < n else float('inf')
if l1 <= r2 and l2 <= r1:
if (m + n) % 2 == 1:
return float(min(r1, r2))
return (max(l1, l2) + min(r1, r2)) / 2.0
elif l1 > r2:
right = i - 1
else:
left = i + 1
Key idea: Binary search on the partition of the shorter array. Find the partition where left halves of both arrays together have exactly half the total elements, with max(left) ≤ min(right).