PYTHON & CODING · QUESTION 87

How does binary search work, and how do you avoid boundary bugs?

On this page

Intermediate 4 min read

Interview-ready answerThe concise version to remember

Binary search finds a target in sorted data by repeatedly comparing with the middle element and discarding the half that cannot contain the answer. It takes O(log n) comparisons. Correctness depends on sorted input and a consistent interval convention; update bounds so each iteration shrinks the search space and test empty, singleton, and boundary cases.

LET'S MAKE IT SIMPLE

First, the idea in plain English

In a sorted list, each comparison tells you whether the target must be to the left or right of the middle. Instead of checking every item, you remove half the remaining possibilities. This is fast, but only if the ordering assumption is true and the loop handles boundaries correctly.

A USEFUL COMPARISON

Picture it this way

Looking up a word in a dictionary, you open near the middle and decide which half could contain it, repeating until the page is found. If the dictionary is not alphabetized, the decision to discard half is invalid.

FOLLOW THE JOURNEY

Each comparison halves a sorted search interval

Trace midpoint checks and interval updates to a found or absent result.

Each comparison halves a sorted search intervalTrace midpoint checks and interval updates to a found or absent result.Algorithm walkthrough

01Set search boundsInitialize the interval that may contain the target.

02Inspect midpointCompare the middle value with the target.

03Shrink intervalMove one bound past the midpoint or return a match.

04Finish safelyStop when no candidate positions remain.

This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; An empty interval means the target is absent.

How to read this visual
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; An empty interval means the target is absent.

UNDER THE HOOD

How it works, step by step

Set search bounds

Initialize the interval that may contain the target.

Why it matters: Clear inclusive or half-open bounds prevent ambiguity.

Inspect midpoint

Compare the middle value with the target.

Why it matters: Sorted order determines which half can be discarded.

Shrink interval

Move one bound past the midpoint or return a match.

Why it matters: The interval must get strictly smaller each iteration.

Finish safely

Stop when no candidate positions remain.

Why it matters: An empty interval means the target is absent.

OUTSIDE THE TEXTBOOK

A practical example

To find an employee ID in a sorted array, compare it with the middle ID. If the target is smaller, continue in the lower half; otherwise search the upper half. A half-open interval `[low, high)` makes the empty condition `low == high` and avoids including the upper endpoint.

GO A LITTLE DEEPER

Technical details that matter

Binary search requires random access or another structure with efficient midpoint access.
Use `mid = low + (high - low) // 2` in fixed-width integer languages to avoid overflow; Python integers do not overflow this way.
Lower-bound and upper-bound variants find insertion positions and duplicates.

Python example

def binary_search(values, target):
    low, high = 0, len(values)
    while low < high:
        middle = (low + high) // 2
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low if low < len(values) and values[low] == target else -1

This half-open implementation finds a lower bound, then checks whether the value at that position equals the target. It returns -1 when absent.

MAKE A GOOD CHOICE

When is this useful?

Searching sorted arrays or indexed ranges.
Finding insertion points and first/last occurrences.
Reducing repeated lookup work in ordered data.

Consider the alternative

Use a hash map for frequent exact lookups when memory is available and order is unnecessary. Use a tree or database index for dynamic ordered data.

WATCH OUT FOR

Common misunderstandings

Applying binary search to unsorted input.
Failing to move a bound past the midpoint.
Mixing inclusive and half-open interval conventions.

REAL-WORLD TRADE-OFFS

Limitations and failure cases

Insertion into a Python list remains O(n) even if position search is O(log n).
Binary search is not efficient on linked lists without random access.
Off-by-one errors are common without stated invariants.

WHAT TO REMEMBER

Key takeaways

1Sorted order enables discarding half the interval each comparison.
2Maintain one interval convention and a shrinking invariant.
3Test empty, singleton, duplicate, and boundary cases.

PRACTICE THE FOLLOW-UP

What might an interviewer ask next?

Why is binary search O(log n)?

Each comparison roughly halves the remaining candidates, so the number of steps grows with the logarithm of input size.

How do you find the first duplicate occurrence?

Continue the search toward the lower bound when values are equal, then verify the resulting position matches the target.

SAY IT OUT LOUD

How to explain this in an interview

“Binary search operates on sorted data. I compare the target with the midpoint and discard the half that cannot contain it, giving O(log n) comparisons. I state an interval convention, ensure each update shrinks the interval, and test empty and boundary cases. If many exact lookups are needed and order does not matter, a hash map may be a better fit.”

Continue your learning path

Connect this question to the roadmap topic it supports.

Open roadmap topic