Lesson 6 of 16 Arrays and Strings

Binary Search Pattern (and on the Answer)

Binary search beyond sorted arrays: lower bound without off-by-one bugs, rotated sorted arrays, and binary search on the answer (Koko eating bananas).

40-50 min intermediate 0/16 lessons done
Course contents Lesson 6 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. The lower-bound template
  4. Code
  5. Recognising “binary search on the answer”
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • One loop invariant that removes off-by-one bugs.
  • Searching a rotated sorted array.
  • Binary search on the answer: when the search space is values, not indices.

Signals

  • Sorted (or rotated sorted) input and O(log n) required.
  • “Minimum value such that…” or “maximum value such that…” where checking a candidate is easy and feasibility is monotonic.
  • Constraints like values up to 10⁹, which rule out trying every value.

The lower-bound template

Search the half-open range [lo, hi). If nums[mid] < target, the answer is right of mid; otherwise mid might be the answer, so keep it with hi = mid. The loop ends when lo == hi, which is the answer. Most binary-search variants reduce to “find the first index where a condition becomes true”.

Code

"""Binary search: on sorted arrays, rotated arrays and on the answer itself."""
import math


def lower_bound(nums, target):
    """First index with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)  # search in [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 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


def min_eating_speed(piles, hours):
    """Smallest speed k so all piles finish within `hours` (binary search on the answer)."""
    def feasible(k):
        return sum(math.ceil(p / k) for p in piles) <= hours

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid   # mid works; maybe something smaller does too
        else:
            lo = mid + 1
    return lo


if __name__ == "__main__":
    print(lower_bound([1, 3, 3, 5, 8], 3), lower_bound([1, 3, 3, 5, 8], 4), lower_bound([1, 3], 9))
    print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0), search_rotated([4, 5, 6, 7, 0, 1, 2], 3))
    print(min_eating_speed([3, 6, 7, 11], 8))

Output:

1 3 2
4 -1
4
  • lower_bound returns the first index ≥ target: 1 for 3, 3 for 4, and len(nums) = 2 when nothing qualifies. Python’s bisect.bisect_left does the same.
  • Rotated array: at least one half around mid is sorted. Check whether the target lies in the sorted half’s range; if not, it’s in the other half.
  • On the answer: for eating speed k, feasible(k) is monotonic: if speed k works, any faster speed works. Find the smallest feasible k between 1 and max(piles). Cost: O(n log max).

Recognising “binary search on the answer”

Ask: “If I guessed the answer, could I check it quickly? And if a guess works, do all larger (or smaller) guesses work?” If yes to both, binary search the guess. Classic examples: ship packages within D days, split array largest sum, minimum days to make bouquets, aggressive cows.

Practise: binary search problems.

Key takeaways

  • Use a half-open [lo, hi) range and “first index where condition holds” to avoid off-by-one bugs.
  • In a rotated array, one half around mid is always sorted; use it to decide.
  • Binary search on the answer needs a fast check and monotonic feasibility.
  • (lo + hi) // 2 is fine in Python; in Java/C++ use lo + (hi - lo) / 2 to avoid overflow.

Exercises

  1. Write upper_bound (first index > target) and use both to count occurrences of a value.
  2. Find the minimum in a rotated sorted array.
  3. Solve “capacity to ship packages within D days” with binary search on the answer.

Quiz

  1. In lower_bound, why is it hi = mid and not hi = mid - 1?
  2. What two properties make binary search on the answer valid?
  3. Why is (lo + hi) / 2 risky in Java?
Show answers
  1. nums[mid] >= target, so mid itself may be the answer and must stay in the range.
  2. A fast feasibility check for a candidate, and monotonic feasibility (once a value works, all larger, or all smaller, values work).
  3. lo + hi can overflow a 32-bit int for large indices; lo + (hi - lo) / 2 avoids it.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).