Command Palette

Search for a command to run...

Hectal

Module 11

Binary Search

Halve the search space at every step: find positions in sorted data, handle rotated arrays, and search over answers instead of indexes.

Intermediate 4 lessons 9 problems ~55 min of lessons
Binary Search on an IndexBinary Search on the Answer

Binary search needs only one thing: a question whose answer flips from "no" to "yes" (or the reverse) exactly once across the search space. Sorted arrays have that property, but so do many problems that never mention sorting, like "what is the smallest speed that finishes in time?".

The module is mostly about getting the details right, because binary search is famously easy to get almost right: the loop condition, how mid is computed, and which half to keep. One reliable template removes most of the bugs.

Best after: Arrays

Part 1

Learn the ideas

  1. 11.1Halving the Search SpaceLook at the middle, decide which half can't contain the answer, and throw it away: about 17 steps for 100,000 items.12 min
  2. 11.2Lower Bound, Upper Bound and One Reliable TemplateMost binary-search bugs come from boundaries. The "first index where a condition is true" template handles first/last positions, insert positions and answers.15 min
  3. 11.3Rotated Sorted ArraysAfter a rotation, at least one half around mid is still sorted. Check which, and whether the target lies inside it.12 min
  4. 11.4Binary Search on the AnswerWhen you can check "is x enough?" and bigger x is always at least as good, binary search the smallest x that works.15 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 11.1Binary SearchEasyBinary Search on an Index

    The classic search, written carefully: loop condition, mid calculation, and half updates.

  2. 11.2Search Insert PositionEasyBinary Search on an Index

    The lower-bound template: the first index whose value is at least the target.

  3. 11.3Find First and Last PositionMediumBinary Search on an Index

    Two boundary searches: lower bound for the first copy, upper bound minus one for the last.

  4. 11.4Search in Rotated Sorted ArrayMediumBinary Search on an Index

    Binary search when sortedness is broken at one point: one half is always sorted, so decide using that half.

  5. 11.5Find Minimum in Rotated Sorted ArrayMediumBinary Search on an Index

    Find the rotation point by comparing mid with the right end: the first-true template again.

  6. 11.6Search a 2D MatrixMediumBinary Search on an Index

    Treat a row-sorted matrix as one virtual sorted array: index i maps to row i / cols, column i % cols.

  7. 11.7Koko Eating BananasMediumBinary Search on the Answer

    Binary search on the answer: test a speed with a quick feasibility check and halve the range of speeds.

  8. 11.8Capacity to Ship Packages Within D DaysMediumBinary Search on the Answer

    A greedy feasibility check (fill each day until the next package won't fit) plus binary search on capacity.

  9. 11.9Median of Two Sorted ArraysHardBinary Search on an Index

    Binary search a partition of the smaller array so that everything on the left is ≤ everything on the right.