Skip to content
Hello Python
Algorithm1 Practice1 Interview

Search

Locate a value, state, path, or feasible answer inside an explicit or implicit search space. 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 Search when the prompt's constraints and required operations match this shape: Locate a value, state, path, or feasible answer inside an explicit or implicit search space.

Pybit demonstrates Search in a professional Python interview workspace.
On this page · Define the Search Space

Checking your account…

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

Search Code Labs

Define the Search Space

Search operates over explicit items, numeric candidates, or implicit states connected by transitions. Define what one state means and which states are legal before choosing an algorithm.

Choose a Frontier Policy

A queue explores by distance, a stack by branch depth, and a priority queue by current best cost. The data structure is the search policy, not an implementation detail.

Trace a Search Frontier

Reference
from collections import deque

def queue_frontier_trace(adjacency,start):
    if start==-1:return []
    queue=deque([start]); seen={start}; trace=[]
    while queue:
        trace.append(list(queue)); node=queue.popleft()
        for neighbor in adjacency[node]:
            if neighbor not in seen: seen.add(neighbor); queue.append(neighbor)
    return trace
Practice

Implement queue_frontier_trace(adjacency,start). Return queue contents before each BFS removal.

Public tests

  • Expose frontier policy

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

Recognize Goal and Repeated State

Test the goal at a consistent point and record visited state before adding duplicates to the frontier. The visited key must include every dimension that changes future behavior.

Find a Reachable Goal

Reference
from collections import deque

def reachable_goal(adjacency,start,goals):
    if start==-1:return -1
    queue=deque([start]); seen={start}
    while queue:
        node=queue.popleft()
        if node in goals:return node
        for neighbor in adjacency[node]:
            if neighbor not in seen:seen.add(neighbor);queue.append(neighbor)
    return -1
Practice

Implement reachable_goal(adjacency,start,goals). Return the first goal found by BFS or -1.

Public tests

  • Stop when the goal contract is met

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

Use linear search for unsorted finite items, binary search for monotone ordered spaces, and graph search for generated transitions with possible branching. Complexity follows inspected states plus generated edges.

Explain It in an Interview

Say: “A state is…, neighbors are…, and this frontier policy guarantees… . I stop under this goal predicate and deduplicate with this key.” Then state completeness, optimality assumptions, and worst-case frontier space.

Python Version Note

Complexity & Invariants

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

OperationAverageWorstInterview note
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 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 Search

Use It When

  • Use 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 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: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

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