EasyDSA9 min read

How does binary search work and what are its requirements?

Q: How does binary search work and what are its requirements?

# How Binary Search Works and What It Requires (Python) **Target Audience:** Beginners preparing for coding interviews; you only need to know arrays and loops. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory. ## 1. Why This Even Matters — A Story First Think of the game "guess my number between 1 and 100", where after each guess you are told "higher" or "lower". A beginner guesses 1, 2, 3, ... and may need 100 tries. A smart player always guesses the middle of what is left: 50, then 25 or 75, and so on. Every answer throws away half of the remaining numbers, so 7 guesses are always enough for 100 numbers, and about 20 for a million. That is binary search. It only works because "hig

1.1k views

3 of 154

The problem

Question presented to candidate: "How does binary search work, and what has to be true about the data for it to work? Please write it in Python and tell me its complexity."

What a strong answer should cover:

The mechanism: keep lo and hi, check the middle, discard the half that cannot contain the target; stop when found or the range is empty.
The requirements: sorted (or monotonic) data, O(1) random access, known bounds and a consistent comparison — and why a linked list does not qualify.
O(log n) time with a concrete number (about 20 steps for a million items), O(1) space iteratively.
Handles duplicates with lower and upper bound, and states the loop invariant to avoid off-by-one errors.
Python specifics: // for the midpoint, ints never overflow, and the bisect module (bisect_left, bisect_right, insort).

Code / implementation expected: Yes — a correct iterative binary search in Python, ideally also the lower-bound variant.

binary-search

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

How Binary Search Works and What It Requires (Python)

Target Audience: Beginners preparing for coding interviews; you only need to know arrays and loops. Difficulty: Easy Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory.

1. Why This Even Matters — A Story First

Think of the game "guess my number between 1 and 100", where after each guess you are told "higher" or "lower". A beginner guesses 1, 2, 3, ... and may need 100 tries. A smart player always guesses the middle of what is left: 50, then 25 or 75, and so on. Every answer throws away half of the remaining numbers, so 7 guesses are always en

The solution is hidden so you can try first

9 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonClassic binary search with a trace and step counts

Practice

PythonLower bound, upper bound, first and last occurrence

Practice

PythonThe standard library way, and midpoint overflow

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 3 of 154 in DSA

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All DSA questions

Up nextEasy→

How do you solve the climbing stairs problem?

Continue