Binary Search: Not Just for Sorted Arrays

Ask most candidates what binary search is for, and you’ll get the same answer: “finding an element in a sorted array.” That answer is technically correct and strategically wrong — and it’s why binary search interview problems have such a brutal failure rate.

Here’s the reframe that changes everything: binary search is a technique for shrinking a search space in half whenever you can answer one yes/no question about the middle. The sorted array is just the most famous search space. Once you see it this way, problems like “minimum eating speed” and “split an array to minimize the largest sum” stop looking like exotic puzzles and start looking like the same 15 lines of code.

In this post we’ll build up from the classic template, generalize it to search on the answer, handle rotated arrays, and then work through six interview problems in Python.

The Classic Template (and the Two Bugs That Kill It)

Let’s get the baseline down first. Binary search on a sorted array:

 1def binary_search(arr, target):
 2    left, right = 0, len(arr) - 1
 3    while left <= right:
 4        mid = left + (right - left) // 2
 5        if arr[mid] == target:
 6            return mid
 7        elif arr[mid] < target:
 8            left = mid + 1
 9        else:
10            right = mid - 1
11    return -1  # Not found

Every comparison eliminates half of the remaining candidates, which is why the runtime is O(log n) — a billion elements takes about 30 steps. If Big-O reasoning is still shaky for you, Day 3: Introduction to Time Complexity covers it from scratch.

Interviewers care less about whether you’ve memorized this and more about whether you avoid the two classic bugs:

  1. Off-by-one boundaries. Should the loop be left <= right or left < right? Should you move to mid + 1 or mid? Mixing conventions between templates causes infinite loops. Pick one invariant and state it out loud: “my answer, if it exists, is always inside [left, right].”
  2. Integer overflow on mid. (left + right) // 2 overflows in fixed-width languages like Java or C++. Python integers don’t overflow, but write left + (right - left) // 2 anyway — interviewers notice, and it signals you’ve thought about it.

Two useful variations — first and last occurrence in an array with duplicates — are covered with full implementations in Day 25: Binary Search and Its Variations. The key change: when you find a match, don’t return — keep shrinking toward the side you care about.

The Big Idea: Search on the Answer

Now for the part almost nobody teaches well.

Suppose a problem asks: “What is the minimum speed / capacity / time X such that some condition holds?” There’s no array to search. But there is a search space: the range of possible answers.

The trick works whenever the condition is monotonic — if speed k is fast enough, every speed greater than k is also fast enough. Picture the answers as a row of booleans:

speed:    1  2  3  4  5  6  7  8
feasible: F  F  F  T  T  T  T  T
                   ^
                   we want the first T

That’s a sorted array of Fs followed by Ts. Finding the boundary is binary search — you just replace arr[mid] == target with a feasibility check can(mid):

1def binary_search_on_answer(lo, hi, can):
2    while lo < hi:
3        mid = lo + (hi - lo) // 2
4        if can(mid):
5            hi = mid      # mid works; try smaller
6        else:
7            lo = mid + 1  # mid fails; must go bigger
8    return lo

The template never changes. The interview problem is really asking two questions:

  1. What is the range of possible answers? (lo, hi)
  2. Given a candidate answer, can I check feasibility efficiently? (can, usually a greedy O(n) pass)

If you can answer both, you’ve solved it. Total cost: O(n log(range)).

Six Interview Problems, One Technique

Problem 1: First Bad Version (classic boundary)

Versions 1..n; all versions after the first bad one are bad. Find the first bad version.

This is the F...FT...T picture in its purest form:

1def first_bad_version(n, is_bad):
2    lo, hi = 1, n
3    while lo < hi:
4        mid = lo + (hi - lo) // 2
5        if is_bad(mid):
6            hi = mid
7        else:
8            lo = mid + 1
9    return lo

If you can solve this, you already understand every problem below — they only differ in how can() is computed.

Problem 2: Koko Eating Bananas (search on answer)

Koko has piles of bananas and h hours. Eating at speed k, a pile of size p takes ceil(p / k) hours. Find the minimum k to finish in time.

  • Answer range: 1 to max(piles).
  • Monotonic? Yes — eating faster never hurts.
 1import math
 2
 3def min_eating_speed(piles, h):
 4    def can(k):
 5        return sum(math.ceil(p / k) for p in piles) <= h
 6
 7    lo, hi = 1, max(piles)
 8    while lo < hi:
 9        mid = lo + (hi - lo) // 2
10        if can(mid):
11            hi = mid
12        else:
13            lo = mid + 1
14    return lo

Problem 3: Ship Packages Within D Days (search on answer)

Packages must ship in order. Find the minimum ship capacity to deliver them all within days days.

  • Answer range: max(weights) (must fit the heaviest package) to sum(weights) (ship everything in one day).
  • Feasibility check: greedily fill each day.
 1def ship_within_days(weights, days):
 2    def can(cap):
 3        used_days, load = 1, 0
 4        for w in weights:
 5            if load + w > cap:
 6                used_days += 1
 7                load = 0
 8            load += w
 9        return used_days <= days
10
11    lo, hi = max(weights), sum(weights)
12    while lo < hi:
13        mid = lo + (hi - lo) // 2
14        if can(mid):
15            hi = mid
16        else:
17            lo = mid + 1
18    return lo

Problem 4: Split Array Largest Sum (search on answer, hard tier)

Split an array into k contiguous subarrays minimizing the largest subarray sum.

This is a famous “hard” problem, but look closely: it’s identical to Problem 3. “Days” become “subarrays,” “capacity” becomes “largest allowed sum.” The can() function is the same greedy pass with used_days <= k. When you point out this equivalence in an interview, you’ve demonstrated exactly the pattern-recognition skill they’re screening for.

The dynamic-programming solution to this problem is O(k·n²); binary search on the answer gets O(n log(sum)). If you want to compare the two mindsets, start with Day 30: Dynamic Programming Introduction.

Problem 5: Search in Rotated Sorted Array

A sorted array was rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]). Find a target in O(log n).

The array isn’t sorted, so what’s the yes/no question about mid? Here it is: at least one half of any rotated array is properly sorted. Figure out which half, check whether the target lies in that half’s range, and discard accordingly:

 1def search_rotated(nums, target):
 2    left, right = 0, len(nums) - 1
 3    while left <= right:
 4        mid = left + (right - left) // 2
 5        if nums[mid] == target:
 6            return mid
 7        if nums[left] <= nums[mid]:          # left half is sorted
 8            if nums[left] <= target < nums[mid]:
 9                right = mid - 1
10            else:
11                left = mid + 1
12        else:                                # right half is sorted
13            if nums[mid] < target <= nums[right]:
14                left = mid + 1
15            else:
16                right = mid - 1
17    return -1

Notice the deeper lesson: we didn’t need a sorted array. We needed enough structure to safely discard half. That’s the real precondition for binary search.

Problem 6: Find Minimum in Rotated Sorted Array

Same setup — find the smallest element.

Compare mid against right. If nums[mid] > nums[right], the “cliff” (rotation point) is to the right of mid; otherwise the minimum is at mid or to its left:

1def find_min(nums):
2    left, right = 0, len(nums) - 1
3    while left < right:
4        mid = left + (right - left) // 2
5        if nums[mid] > nums[right]:
6            left = mid + 1
7        else:
8            right = mid
9    return nums[left]

Squint and you’ll see First Bad Version again: elements after the rotation point are “bad” (smaller than nums[right] region), and we’re finding the boundary.

In a live interview, run this checklist when a problem smells like optimization:

  • The answer is a number in a bounded range (a speed, a capacity, a distance, a time).
  • The problem says “minimum X such that…” or “maximum X such that…”.
  • Feasibility is monotonic: if an answer works, everything on one side of it also works.
  • You can check a candidate answer faster than you can compute the answer directly — usually with a greedy or counting pass.

If all four boxes tick, say the magic sentence: “The feasibility function is monotonic over the answer space, so I’ll binary search on the answer.” Then write the template you already know.

A word of honest caution: binary search is famously easy to get almost right. Donald Knuth noted that although the algorithm was published in 1946, the first bug-free version for arbitrary array sizes didn’t appear until 1962. Drill the boundary invariants until they’re automatic — that’s practice, not talent.

Where to Go Next

Binary search on the answer shows up constantly in FAANG loops precisely because it separates people who memorized “sorted array lookup” from people who understand search spaces. It’s Day 25 of our structured curriculum, sequenced after arrays and recursion so the prerequisites are already in place.

If you’d rather follow a plan than wander through random problem lists, the full 60-day curriculum takes you from arrays to dynamic programming one day at a time — create a free account to track your progress and unlock the full lessons. And if recursion still feels wobbly (it powers the recursive binary search variant too), read Recursion for Interviews: Think Before You Code next.

Happy searching — may your search space always shrink by half.