Skip to content
Hello Python
Algorithm1 Practice14 Interview

Binary Search

Repeatedly halve an ordered or monotone search space using a boundary invariant. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Binary Search when the prompt's constraints and required operations match this shape: Repeatedly halve an ordered or monotone search space using a boundary invariant.

Pybit demonstrates Binary Search in a professional Python interview workspace.
On this page · Search a Monotone Boundary

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Binary Search Code Labs

Search a Monotone Boundary

Binary search is not merely “search a sorted array.” It searches a monotone decision space: once a predicate becomes true, it stays true, or comparisons consistently discard one side. Prove that shape before writing the loop.

Write the Loop Invariant

For half-open [left, right), state that every index before left is known false and the first true boundary, if it exists, lies inside the unresolved interval. Each iteration must preserve that invariant and strictly shrink the interval.

Trace Exact-Search Decisions

Reference
def binary_search_decisions(values, target):
    left, right = 0, len(values) - 1
    decisions = []
    while left <= right:
        mid = (left + right) // 2
        decisions.append(mid)
        if values[mid] == target:
            break
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return decisions
Practice

Implement binary_search_decisions(values, target). values is sorted. Return the indexes inspected by a standard inclusive binary search, stopping when target is found or the interval is empty.

Public tests

  • Trace inspected midpoints

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Exact Search or First True

Exact search can stop on equality and often uses an inclusive right edge. Boundary search continues after finding a true candidate, retaining it while searching left. Pick one template deliberately; mixing their update rules creates skipped candidates or infinite loops.

Find the First True Boundary

Reference
def find_first_true(flags):
    left, right = 0, len(flags)
    while left < right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid
        else:
            left = mid + 1
    return left
Practice

Implement find_first_true(flags). flags contains zero or more False values followed by zero or more True values. Return the index of the first True value, or len(flags) when no True value exists.

Public tests

  • Verify Find the First True Boundary behavior

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Binary Search or a Hash Lookup

Use binary search when order or a monotone answer space already exists and O(log n) queries are sufficient. Use a hash lookup for average O(1) membership when ordering is irrelevant and extra space is acceptable. Sorting solely for one lookup usually costs more than a scan.

Explain It in an Interview

Say: “The predicate is monotone. My half-open interval contains every possible boundary; false discards through mid, true retains mid. The interval shrinks every iteration.” Then cover the empty input and no-true sentinel, and derive O(log n) time from repeated halving and O(1) space.

The Python bisect reference(opens in a new tab) provides library boundary semantics. Cutting Ribbons(opens in a new tab) transfers the same proof to a numeric answer space.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Binary Search complete workflowO(log n)O(log n)A monotone predicate with one boundary is a direct lower-bound search even when the desired item is absent. Every index before left is known false, while every index at or after right is known true or the sentinel len(flags).

Space

O(1) for the focused Find the First True Boundary implementation.

Assumptions

  • Each midpoint test preserves the half-open partition: a true midpoint becomes the new possible boundary, while a false midpoint and everything before it are discarded. Convergence leaves left at the first true index or the sentinel.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Binary Search invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The unresolved search region still contains every possible answer.
  3. Each transition inspects or eliminates new work and therefore makes progress.
  4. A monotone predicate with one boundary is a direct lower-bound search even when the desired item is absent. Preserve this claim after every transition.
  5. Every index before left is known false, while every index at or after right is known true or the sentinel len(flags). Preserve this claim after every transition.

When To Use Or Avoid Binary Search

Use It When

  • Use Binary Search when this precondition is stated or can be proved: The search space and equality or monotone-boundary contract are explicit.
  • Use it when this maintained state removes repeated work: The unresolved search region still contains every possible answer.

Choose Another Tool When

  • Avoid Binary Search when this precondition is absent: The search space and equality or monotone-boundary contract are explicit.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The search space and equality or monotone-boundary contract are explicit.

Avoid

def find_first_true(flags):
    pass

Use instead

def find_first_true(flags):
    left, right = 0, len(flags)
    while left < right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Find the First True Boundary(opens in a new tab)

Breaking the state transition

Uses -1 instead of the required insertion boundary when the monotone sequence contains no true value.

Prevent it: Preserve this proof obligation: Every discarded candidate or interval is excluded by a direct comparison or monotone predicate.

Avoid

def find_first_true(flags):
    left, right = 0, len(flags) - 1
    while left <= right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return left if left < len(flags) else -1

Use instead

def find_first_true(flags):
    left, right = 0, len(flags)
    while left < right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Find the First True Boundary(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(log n).

Avoid

def find_first_true(flags):
    left, right = 0, len(flags) - 1
    while left <= right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return left if left < len(flags) else -1

Use instead

def find_first_true(flags):
    left, right = 0, len(flags)
    while left < right:
        mid = (left + right) // 2
        if flags[mid]:
            right = mid
        else:
            left = mid + 1
    return left

Where you will hit this: Cutting Ribbons(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.