Modified Binary Search

Q: What is binary search on the answer?

Instead of searching an array, you binary search the range of possible answers and use a feasibility check as the comparison. It applies when the question asks for a minimum or maximum feasible value and feasibility is monotone — if a value works, every larger (or smaller) one does too. Koko Eating Bananas and Split Array Largest Sum are the standard examples.

Q: How do you binary search a rotated sorted array?

At every step one half is still sorted, and comparing nums[lo] with nums[mid] tells you which. Check whether the target falls inside that sorted half's range: if it does, search there, otherwise search the other half. Each step still halves the range, so it stays O(log n).

Q: Why does my binary search loop forever?

Almost always a mismatched convention. With while lo < hi use hi = mid and lo = mid + 1; with while lo <= hi use hi = mid - 1 and lo = mid + 1. Combining lo <= hi with hi = mid leaves the range unchanged when lo == hi, so it never terminates.

Everyone can write binary search on a sorted array. What gets asked is the two variants where the array is not sorted the way you expect, or where there is no array at all — and both are approachable once you stop writing binary search as "find the target" and start writing it as "find the boundary".

The template worth memorising

Forget if arr[mid] == target: return mid. Use the half-open boundary form, which finds the first index satisfying a predicate and never needs an off-by-one argument:

def lower_bound(lo, hi, predicate):
    """First value in [lo, hi) where predicate is True.
       Requires predicate to be False...False, True...True."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid            # mid might be the answer — keep it
        else:
            lo = mid + 1        # mid definitely is not
    return lo

/** First value in [lo, hi) where the predicate holds.
    Requires the predicate to be false...false, true...true. */
int lowerBound(int lo, int hi, IntPredicate predicate) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // never (lo + hi) / 2 — that overflows
        if (predicate.test(mid)) {
            hi = mid;           // mid might be the answer — keep it
        } else {
            lo = mid + 1;       // mid definitely is not
        }
    }
    return lo;
}

/* First value in [lo, hi) where the predicate holds. */
int lowerBound(int lo, int hi, const function<bool(int)>& predicate) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // never (lo + hi) / 2 — that overflows
        if (predicate(mid)) {
            hi = mid;           // mid might be the answer — keep it
        } else {
            lo = mid + 1;       // mid definitely is not
        }
    }
    return lo;
}

/* First value in [lo, hi) where the predicate holds. */
int lowerBound(int lo, int hi, int (*predicate)(int)) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   /* never (lo + hi) / 2 — overflows */
        if (predicate(mid)) {
            hi = mid;           /* mid might be the answer — keep it */
        } else {
            lo = mid + 1;       /* mid definitely is not */
        }
    }
    return lo;
}

/** First value in [lo, hi) where the predicate holds.
    Requires the predicate to be false...false, true...true. */
function lowerBound(lo, hi, predicate) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (predicate(mid)) {
      hi = mid;          // mid might be the answer — keep it
    } else {
      lo = mid + 1;      // mid definitely is not
    }
  }
  return lo;
}

Everything else is a choice of predicate:

Every binary search variant is this picture. Find the first True; the predicate is what changes between problems.

Want	Predicate
First index with `arr[i] >= target`	`arr[mid] >= target`
First index with `arr[i] > target`	`arr[mid] > target`
Last index with `arr[i] <= target`	`lower_bound(...) - 1`
First/last position of a value	both of the above

lo < hi (not <=), hi = mid (not mid - 1), lo = mid + 1. Those three together are what make the loop always terminate and always land on the boundary. Use lo + (hi - lo) // 2 out of habit — in Java or C++ the naive (lo + hi) / 2 overflows, and it is a thing interviewers notice.

Rotated sorted arrays

A rotated array is not sorted, but one half always is, and you can tell which by comparing arr[lo] to arr[mid]. Decide whether the target lies inside the sorted half; if it does, recurse there, otherwise recurse into the other one.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                  # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                      # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

int searchRotated(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {               // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                   // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int searchRotated(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {               // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                   // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int searchRotated(int* nums, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {               /* left half is sorted */
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                   /* right half is sorted */
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;

    if (nums[lo] <= nums[mid]) {                // left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                    // right half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Find Minimum in Rotated Sorted Array is the same insight, simpler: compare nums[mid]

to nums[hi]. If nums[mid] > nums[hi] the pivot is to the right, so lo = mid + 1; otherwise hi = mid. Comparing against nums[lo] instead is the version that breaks on an unrotated array.

Binary search on the answer

The variant that does not look like binary search at all, and the one worth the most marks. When the question asks for a minimum feasible value and feasibility is monotone — if speed 5 works then speed 6 certainly does — you can binary search the answer space directly, with a simulation as the predicate.

def min_eating_speed(piles, hours):
    def can_finish(speed):
        return sum(-(-p // speed) for p in piles) <= hours   # ceil division

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

int minEatingSpeed(int[] piles, int hours) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, hours)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean canFinish(int[] piles, int speed, int hours) {
    long total = 0;
    for (int p : piles) total += (p + speed - 1) / speed;   // ceil division
    return total <= hours;
}

bool canFinish(const vector<int>& piles, int speed, int hours) {
    long long total = 0;
    for (int p : piles) total += (p + speed - 1) / speed;   // ceil division
    return total <= hours;
}

int minEatingSpeed(const vector<int>& piles, int hours) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, hours)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

static bool canFinish(int* piles, int n, int speed, int hours) {
    long long total = 0;
    for (int i = 0; i < n; i++) total += (piles[i] + speed - 1) / speed;
    return total <= hours;      /* ceil division without floating point */
}

int minEatingSpeed(int* piles, int n, int hours) {
    int lo = 1, hi = 0;
    for (int i = 0; i < n; i++) if (piles[i] > hi) hi = piles[i];

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, n, mid, hours)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

function minEatingSpeed(piles, hours) {
  const canFinish = (speed) =>
    piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0) <= hours;

  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canFinish(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

The recognition cue is a question phrased as minimise the maximum or *maximise the minimum* — Koko Eating Bananas, Capacity To Ship Packages Within D Days, Split Array Largest Sum are all the same problem with different simulations. Three things to identify out loud: the search range, the feasibility check, and why feasibility is monotone.

Median of Two Sorted Arrays

The Hard one. It is not a search over values but over partitions: binary search the smaller array for the cut point that puts exactly half the combined elements on the left, checking maxLeftA <= minRightB and maxLeftB <= minRightA. Always search the smaller array so the index arithmetic stays in range, and use ±infinity sentinels at the edges instead of writing four boundary branches.

Complexity

O(log n) for array searches. Binary search on the answer is O(log(range) × cost of the check) — for Koko that is O(n log(max pile)), which is the point: the simulation runs a logarithmic number of times instead of once per candidate. Median of Two Sorted Arrays is O(log min(m, n)).

Mistakes that cost the round

Mixing loop conventions. lo <= hi with hi = mid is an infinite loop; lo < hi

with hi = mid - 1 skips the answer. Pick one form and keep it consistent.

`(lo + hi) // 2` in a language with fixed-width ints.
Comparing against `nums[lo]` in Find Minimum, which fails on an already-sorted array.
Not checking monotonicity before binary searching an answer space. If feasibility can

flip back and forth, the search is unsound.

Duplicates in a rotated array. nums[lo] == nums[mid] makes it impossible to tell

which half is sorted; the fix is to shrink lo by one, which degrades to O(n) worst case.

What to drill

Binary Search — the boundary template.
Find First and Last Position of Element — two boundaries.
Search in Rotated Sorted Array — pick the sorted half.
Find Minimum in Rotated Sorted Array — compare against hi.
Koko Eating Bananas — search the answer.
Capacity To Ship Packages Within D Days — the same, restated.
Split Array Largest Sum — minimise the maximum.
Median of Two Sorted Arrays — search the partition.

All on the 22 DSA Patterns sheet.

Frequently asked

What is binary search on the answer?

Instead of searching an array, you binary search the range of possible answers and use a feasibility check as the comparison. It applies when the question asks for a minimum or maximum feasible value and feasibility is monotone — if a value works, every larger (or smaller) one does too. Koko Eating Bananas and Split Array Largest Sum are the standard examples.

How do you binary search a rotated sorted array?

At every step one half is still sorted, and comparing nums[lo] with nums[mid] tells you which. Check whether the target falls inside that sorted half's range: if it does, search there, otherwise search the other half. Each step still halves the range, so it stays O(log n).

Why does my binary search loop forever?

Almost always a mismatched convention. With while lo < hi use hi = mid and lo = mid + 1; with while lo <= hi use hi = mid - 1 and lo = mid + 1. Combining lo <= hi with hi = mid leaves the range unchanged when lo == hi, so it never terminates.