TRT
Sign in

Core · Module 9 · Lesson 3 of 4

Searching an answer space

When a yes-or-no check about a candidate answer flips exactly once, from no to yes, you can binary search over the answers themselves, even when no array exists.

Pro — members onlyAbout 14 minutes

By the end you can

  • Recognize problems whose feasibility check is monotonic in the answer
  • Binary search the smallest feasible answer, with correct bounds and a feasibility function
  • Estimate the cost as the number of halvings times the cost of one check

Builds on Lower and upper bounds.

01 · A question first

Koko has 8 hours to eat four piles of bananas, of sizes 3, 6, 7 and 11, and eats at most k bananas per hour. What is the slowest speed k that lets her finish? There is no sorted array to search, yet binary search finds the answer in four checks. What is it searching?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Searching without an array
  • The recipe
  • Recognizing the pattern
  • Real answers, real numbers
  • Binary search outside algorithms
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeKoko eating bananasFind the slowest eating speed that finishes all piles within h hours, by binary searching over speeds with a feasibility check.Practice · medium · LeetCodeCapacity to ship packages within D daysFind the smallest ship capacity that delivers packages in order within D days, by binary searching capacities with a greedy check.Practice · hard · LeetCodeMedian of two sorted arraysFind the median of two sorted arrays in O(log min(m, n)) by binary searching for the cut that splits all elements in half.

Asked in interviews

Something wrong with this lesson? Report a problem