0x50Lesson 6 of 13

Halve the search space with binary search

Search sorted data - or any monotonic condition - in O(log n).

20 min 5-question quiz 1 code exercise

By the end of this lesson you can

Write a bug-free binary search.
Find the first position where a condition becomes true.
Recognize binary search on answers, not just arrays.

Binary search repeatedly halves a sorted search space: compare the middle element, then discard the half that cannot contain the answer. A million items take about 20 steps. Beyond finding a value in a sorted array, it solves any problem where a yes/no condition flips exactly once - “the first bad version”, “the smallest capacity that ships all packages in D days”.

A template that avoids off-by-one bugs

Use a half-open range [low, high) and find the first index where a condition is true:

Start with low = 0, high = len(nums).
While low < high: take mid = (low + high) // 2.
If the condition holds at mid, the answer is at mid or to its left: high = mid. Otherwise it is to the right: low = mid + 1.
When the loop ends, low is the first index where the condition holds (or len(nums) if none does).

solution.py

1def first_at_least(nums, target):
2    low, high = 0, len(nums)
3    while low < high:
4        mid = (low + high) // 2
5        if nums[mid] >= target:
6            high = mid
7        else:
8            low = mid + 1
9    return low
10
11nums = [1, 3, 5, 7, 9]
12print(first_at_least(nums, 5), first_at_least(nums, 6), first_at_least(nums, 10))

Output

2 3 5

This “lower bound” search answers several questions at once: whether the target exists (low < len(nums) and nums[low] == target), where to insert it to keep the list sorted, and how many elements are smaller than it. Python’s bisect.bisect_left implements exactly this.

Key takeaways

Binary search needs sorted data or a condition that flips once.
Use one template consistently; the half-open version finds the first true position.
You can binary-search over possible answers, not just indices.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: solve interview problems

Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.

Exercise 1

Find the insert position

+25 XP

Read a line of distinct integers sorted in ascending order, then a target. Print the index of the target if present; otherwise the index where it would be inserted to keep the list sorted. Use binary search.

Target present
Insert in the middle
Insert at the end
Insert at the start

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…