DSA · Lesson 7 of 9

Binary search

Halving the search space on sorted data — and on answers.

On sorted data, binary search checks the middle element and discards the half that can't contain the target, giving O(log n). A million items need at most about 20 checks.

Get the details right — they are where interview bugs hide:

Loop while lo <= hi for an exact-match search.
Compute mid = (lo + hi) // 2.
Move lo = mid + 1 or hi = mid - 1 so the range always shrinks.

Binary search on the answer: when “can we do it with X?” is false up to some point and true after, search for the smallest X that works — e.g. minimum daily capacity to finish tasks in D days. Python's bisect module does insert-position searches.

Try it yourself

Code editor

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Requires sorted data (or a monotonic yes/no answer).
O(log n) — each step halves the range.
Watch loop condition and mid ± 1 updates.

Quick check

About how many steps does binary search need for 1,000,000 sorted items?

~20 ~1,000 ~500,000 ~1,000,000

Practice task

Write first_occurrence(nums, target) that returns the index of the first copy of target in a sorted list with duplicates.

Interview corner

Why use lo + (hi - lo) // 2 in some languages?

In languages with fixed-size integers (Java, C++), lo + hi can overflow. Python integers don't overflow, but the habit is good.

What does 'binary search on the answer' mean?

Searching over possible answer values instead of array indexes, using a feasibility check that is false then true as the value grows.