Binary Search Applications Beyond Arrays

Direct Answer

Yes - binary search works on any monotonic search space, not just arrays. If you can write a decision function feasible(x) that is false up to some point and then true forever after (or vice versa), you can binary search for the boundary. This 'binary search on the answer' solves problems like minimum shipping capacity, Koko eating bananas, and integer square root in O(log(range) x cost-of-check).

Deep Dive & Architecture

Binary search is not limited to locating an item in an array. It works on any ordered answer space with a monotonic test: once an answer becomes valid, all larger answers stay valid, or once it becomes invalid, all larger answers stay invalid.

Example: minimum server capacity

Suppose a job must finish within 8 hours. Define canFinish(capacity) to simulate the work and return whether that capacity is enough. Capacity 10 might fail, while 20 succeeds. If 20 succeeds, every capacity above 20 also succeeds. Binary search can find the first successful capacity without checking every number between the lower and upper bounds.

The same idea finds an integer square root, the smallest shipping capacity for a deadline, the minimum eating speed, or the largest feasible distance between placed items. The array is replaced by possible answers, and comparison with a target is replaced by a yes/no feasibility function.

Correctness depends on three things: prove the test is monotonic, choose bounds that contain the answer, and decide whether the boundary sought is the first valid or last valid value. If validity can switch back and forth, binary search is not applicable. With a logarithmic number of tests, total cost is O(log R × cost of one test), where R is the answer range.

Code Example

// Minimum eating speed so all piles finish within h hours.
int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;          // candidate speed
        if (feasible(piles, h, mid)) hi = mid; // works -> try slower
        else lo = mid + 1;                     // too slow -> speed up
    }
    return lo;
}
boolean feasible(int[] piles, int h, int speed) {
    long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceil divide
    return hours <= h;
}

// piles={3,6,7,11}, h=8: speeds 1..11.
// feasible: F F F T T... -> binary search lands on speed 4.

Common Mistakes & Pitfalls

Believing binary search needs a physical sorted array, so missing optimization problems that have no array