All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›Binary Search — Advanced Applications

Binary Search — Advanced Applications

0/12 in this phase0/57 across the roadmap

📖 Concept

Beyond basic search, binary search has powerful advanced applications: search on answer space, finding boundaries, and searching in modified arrays.

Binary Search on Answer Space: When the answer lies in a range [lo, hi] and you can test if a value is feasible:

while (lo < hi):
    mid = (lo + hi) / 2
    if (condition(mid)): hi = mid    // mid works, try smaller
    else: lo = mid + 1               // mid doesn't work, try larger
return lo

Common applications:

  1. Minimize the maximum — split array, ship packages (binary search on max value)
  2. Maximize the minimum — aggressive cows, place elements (binary search on min value)
  3. Find first true — search for transition point in monotonic boolean function
  4. Koko eating bananas — binary search on eating speed

Key insight: Binary search works whenever there's a monotonic condition — once it becomes true, it stays true (or vice versa).

🏠 Real-world analogy: Binary search on answer is like guessing a price. "Is $100 enough?" "Yes." "Is $50 enough?" "No." "Is $75 enough?" "Yes." You narrow down to the exact minimum price.

💻 Code Example

codeTap to expand ⛶
1// FIND FIRST TRUE — Generalized binary search
2function findFirstTrue(lo: number, hi: number, condition: (mid: number) => boolean): number {
3  while (lo < hi) {
4    const mid = lo + Math.floor((hi - lo) / 2);
5    if (condition(mid)) hi = mid;
6    else lo = mid + 1;
7  }
8  return lo;
9}
10

11// KOKO EATING BANANAS — Binary search on speed
12function minEatingSpeed(piles: number[], h: number): number {
13  let lo = 1, hi = Math.max(...piles);
14  while (lo < hi) {
15    const mid = lo + Math.floor((hi - lo) / 2);
16    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
17    if (hours <= h) hi = mid;  // Can eat slower
18    else lo = mid + 1;         // Need to eat faster
19  }
20  return lo;
21}
22

23// SPLIT ARRAY LARGEST SUM — Minimize the maximum sum
24function splitArray(nums: number[], k: number): number {
25  let lo = Math.max(...nums);
26  let hi = nums.reduce((a, b) => a + b, 0);
27  while (lo < hi) {
28    const mid = lo + Math.floor((hi - lo) / 2);
29    if (canSplit(nums, k, mid)) hi = mid;
30    else lo = mid + 1;
31  }
32  return lo;
33}
34

35function canSplit(nums: number[], k: number, maxSum: number): boolean {
36  let groups = 1, currentSum = 0;
37  for (const n of nums) {
38    if (currentSum + n > maxSum) { groups++; currentSum = 0; }
39    currentSum += n;
40  }
41  return groups <= k;
42}
43

44// FIND PEAK ELEMENT — O(log n)
45function findPeakElement(nums: number[]): number {
46  let lo = 0, hi = nums.length - 1;
47  while (lo < hi) {
48    const mid = lo + Math.floor((hi - lo) / 2);
49    if (nums[mid] > nums[mid + 1]) hi = mid;
50    else lo = mid + 1;
51  }
52  return lo;
53}
54

55// SEARCH IN 2D SORTED MATRIX
56function searchMatrix(matrix: number[][], target: number): boolean {
57  const m = matrix.length, n = matrix[0].length;
58  let lo = 0, hi = m * n - 1;
59  while (lo <= hi) {
60    const mid = lo + Math.floor((hi - lo) / 2);
61    const val = matrix[Math.floor(mid / n)][mid % n];
62    if (val === target) return true;
63    if (val < target) lo = mid + 1;
64    else hi = mid - 1;
65  }
66  return false;
67}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Find the square root of a number using binary search (integer part)
  2. Find peak element in an array
  3. Koko eating bananas — find minimum eating speed
  4. Ship packages within D days — find minimum ship capacity
  5. Split array largest sum — minimize the maximum subarray sum
  6. Aggressive cows — maximize minimum distance between cows
  7. Find minimum in rotated sorted array
  8. Median of two sorted arrays (O(log(min(m,n))))
  9. Magnetic force — maximize minimum distance (binary search on answer)
  10. Find kth smallest element in a sorted matrix

⚠️ Common Mistakes

  • Using lo <= hi when you should use lo < hi (or vice versa) — depends on the variant

  • Not identifying the monotonic condition — binary search on answer ONLY works when the feasibility is monotonic

  • Wrong initialization of lo/hi bounds — lo should be the minimum possible answer, hi the maximum

  • Not handling edge cases: single element, all same elements, empty input

  • Infinite loop when lo = hi - 1 and mid = lo always — ensure the search space shrinks each iteration

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Binary Search — Advanced Applications

← PreviousPrefix Sum & Range QueriesNext →Fast & Slow Pointers (Floyd's Cycle Detection)