DEV Community

Dev Cookies
Dev Cookies

Posted on

Binary Search Patterns Series — Blog 2: Monotonic Functions & Answer Search

1. Concept

Unlike classic binary search on arrays, here we are searching for an “answer”. We have:

  • A monotonic function f(x) (either increasing or decreasing)
  • A condition we want to satisfy, e.g., f(x) >= target
  • We want the minimum or maximum x satisfying the condition

Template:

long low = 0, high = 1_000_000_000; // search space while (low < high) { // note: strict < for answer search long mid = low + (high - low) / 2; if (check(mid)) high = mid; // condition satisfied, try smaller else low = mid + 1; // condition not satisfied, increase } return low; // smallest x satisfying condition
Enter fullscreen mode Exit fullscreen mode

2. Key Tips for Answer Search

  1. Use low < high instead of low <= high → Ensures convergence without infinite loop
  2. Always check bounds → Ensure low and high cover the full possible answer space
  3. Avoid integer overflow → mid = low + (high - low)/2
  4. Define a check(mid) function → Returns true if condition satisfied

3. Classic Examples

3.1 Koko Eating Bananas

Problem:
Koko can eat k bananas per hour. Given piles and h hours, find minimum k to finish all bananas.

public int minEatingSpeed(int[] piles, int h) { int low = 1, high = Arrays.stream(piles).max().getAsInt(); while (low < high) { int mid = low + (high - low) / 2; if (canFinish(piles, mid, h)) high = mid; // possible, try smaller else low = mid + 1; // not enough, increase } return low; } private boolean canFinish(int[] piles, int k, int h) { int hours = 0; for (int pile : piles) { hours += (pile + k - 1) / k; // ceiling division } return hours <= h; }
Enter fullscreen mode Exit fullscreen mode

3.2 Capacity to Ship Packages Within D Days 

public int shipWithinDays(int[] weights, int D) { int low = Arrays.stream(weights).max().getAsInt(); int high = Arrays.stream(weights).sum(); while (low < high) { int mid = low + (high - low)/2; if (canShip(weights, D, mid)) high = mid; else low = mid + 1; } return low; } private boolean canShip(int[] weights, int D, int cap) { int days = 1, current = 0; for (int w : weights) { if (current + w > cap) { days++; current = 0; } current += w; } return days <= D; }
Enter fullscreen mode Exit fullscreen mode

3.3 Minimum Time to Complete Tasks

Problem: You have n workers, each worker takes time[i] per task. Find the minimum time to complete totalTasks.

public long minTime(int[] time, long totalTasks) { long low = 1, high = (long)1e18; while (low < high) { long mid = low + (high - low)/2; if (canComplete(time, totalTasks, mid)) high = mid; else low = mid + 1; } return low; } private boolean canComplete(int[] time, long totalTasks, long t) { long count = 0; for (int i : time) { count += t / i; if (count >= totalTasks) return true; } return count >= totalTasks; }
Enter fullscreen mode Exit fullscreen mode

4. Edge Cases

  1. Single-element arrays → check if your low and high cover all possibilities
  2. Very large numbers → always use long for sum/multiplication
  3. Strict inequality → choose < or <= carefully in while loop
  4. Ceiling division → (x + y - 1)/y for integer math

5. Problems to Practice

  • LeetCode 875: Koko Eating Bananas
  • LeetCode 1011: Capacity to Ship Packages Within D Days
  • LeetCode 774: Minimize Max Distance to Gas Station
  • LeetCode 275: H-Index II
  • Binary search on “minimize/maximize” problems

✅ Blog 2 Summary:
We learned how to apply binary search on answers rather than array elements:

  • Monotonic functions
  • “Check” function pattern
  • Minimize / maximize patterns
  • Koko eating bananas, ship packages, minimum time tasks

Next in Series — Blog 3

Binary Search on Rotated & Special Arrays:

  • Rotated sorted arrays with or without duplicates
  • Bitonic / mountain arrays
  • Pivot search patterns
  • Java code with diagrams and examples

Top comments (0)