Skip to content
Data Structures & Algorithms

Searching Algorithms interview questions and answers

59 questions, 28 with code. About 4 h 51 min to read them all.

By TestLab · Updated

Plan for an interview
59 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is linear search in algorithms?

Linear search, also called sequential search, checks each element of a collection in order until it finds the target or exhausts the search space. It works on sorted and unsorted data but takes O(n) time in the worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an array of length n, linear search compares the target with elements at indices 0, 1, 2, and so on:

  1. Start at the first element.

  2. Compare the current element with the target.

  3. Return the index immediately when they match.

  4. If no match appears before the end, report that the target was not found.

This approach is commonly used when data is unsorted, the collection is small, or sorting would cost more than performing one search.

Complexity

Let n be the number of elements being searched.

Case Time Reason
Best O(1) The first element matches the target.
Average O(n) The target is expected to appear somewhere among the elements.
Worst O(n) The target is last or absent, so every element is checked.
  • Auxiliary space: O(1) because only a small number of variables, such as the current index, are needed.

  • Total space: O(n) when the input collection is included.

  • There is no recursive call stack.

  • Linear search is not amortized; each search independently performs up to n comparisons.

Example Walkthrough

Suppose the array is [12, 7, 25, 7, 30] and the target is 7.

Step Index Value Result
1 0 12 Not equal; continue.
2 1 7 Match found at index 1.

A search for 25 would check indices 0, 1, and 2 before returning index 2. A search for 40 would inspect all five elements and return “not found.”

Linear Search vs. Binary Search

Approach Time Space Requirement Best Use
Linear search O(n) average and worst O(1) auxiliary No ordering required Small or unsorted collections
Binary search O(1) best; O(log n) average and worst O(1) auxiliary for iterative search; O(log n) including the recursion stack for recursive search Sorted data or a monotonic condition Large, repeatedly searched collections

The iterative binary-search implementation uses only search bounds and a midpoint, while a recursive implementation adds up to O(log n) stack frames.

Sorting an unsorted collection so binary search can be used may take O(n log n) time and O(1) auxiliary space for a standard in-place algorithm. Therefore, for only one search over unsorted data, linear search may be more efficient overall.

Edge Cases and Variations

  • Empty input: Return “not found” without performing comparisons.

  • One element: The only possible match is checked in O(1) time.

  • Duplicates: Returning the first match gives the lowest index; scanning the entire collection can find every occurrence.

  • Negative numbers: They require no special handling.

  • Already sorted input: Linear search still works, although binary search is faster when many searches are expected.

  • Repeated searches: If the same collection is searched frequently, sorting it and using binary search may be worthwhile.

Common Pitfalls and Interview Tips

  • Start the index at 0 and use the condition index < len(collection) to avoid an out-of-bounds access.

  • Decide whether the function should return the first matching index, all matching indices, or the element itself.

  • Do not use list.pop(0) or list.insert(0, value) to simulate a search; these operations are O(n) and can hide the linear-search behavior.

  • Do not claim linear search is O(log n); its worst-case time is O(n) because it may inspect every element.

  • A common follow-up asks how linear search can find the first occurrence, the last occurrence, or the number of occurrences while retaining O(n) time and O(1) auxiliary space.

3

How do binary search and linear search differ?

Binary search repeatedly eliminates half of a sorted search interval, while linear search examines elements sequentially. Binary search is faster for large sorted collections with efficient random access, whereas linear search works with unsorted data and has simpler implementation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Linear search: Checks each element from the beginning until it finds the target or exhausts the collection.

  • Binary search: Compares the target with the middle element and discards the half that cannot contain the target.

  • Sorted-data requirement: Binary search requires ascending or descending order, or another reliably monotonic condition. Linear search has no ordering requirement.

  • Random-access requirement: Standard binary search needs constant-time access to the midpoint, as provided by arrays and Python lists. On a linked list, midpoint lookup is O(n), so binary search does not provide O(log n) search time.

For binary search, use an inclusive interval [lo, hi] and calculate the midpoint as mid = lo + (hi - lo) // 2. In languages with fixed-width signed integers, this form avoids overflow that could occur with (lo + hi) // 2.

Complexity Comparison

Approach Best time Average time Worst time Auxiliary space When to use
Linear search O(1) O(n) O(n) O(1) Small or unsorted collections; one-off searches
Binary search O(1) O(log n) O(log n) O(1) Large sorted collections with random access or repeated searches
  • Linear search: In the best case, the first element matches. In the average and worst cases, it examines a substantial portion of the n elements.

  • Binary search: In the best case, it finds the midpoint immediately. In the average and worst cases, it requires logarithmically many comparisons because each iteration halves the remaining interval.

  • Space: Both use O(1) auxiliary space, excluding the input collection. Neither requires a recursion stack when implemented iteratively.

Binary Search Variants

  • Lower and upper bounds: bisect_left and bisect_right in Python find insertion positions in a sorted list. bisect_left(values, target) returns the first index where target could be inserted while preserving order; bisect_right(values, target) returns the position after all existing occurrences.

  • First and last occurrence: Use the lower bound for the first occurrence and the upper bound minus one for the last. Both are O(log n).

  • Rotated sorted array: A modified binary search can locate a target in an ascending array rotated at an unknown pivot in O(log n) when elements are distinct. Handling duplicates can degrade the worst case to O(n).

  • Binary search on an answer: Search a numeric range rather than an array when a feasibility condition is monotonic. For example, finding the minimum shipping capacity uses O(log R) time, where R is the size of the capacity range.

Example Walkthrough

Search for 8 in [2, 4, 4, 8, 10]:

  1. Linear search compares 2, 4, 4, and 8, requiring four comparisons.

  2. Binary search starts with [lo, hi] = [0, 4] and mid = 2.

  3. The value at index 2 is 4. Since 8 > 4, the next interval is [3, 4].

  4. Its midpoint is index 3, where the value is 8, so the target is found in two comparisons.

For the duplicated value 4, bisect_left returns index 1, while bisect_right returns index 3. Therefore, the first occurrence is at index 1 and the last is at index 2.

Common Pitfalls

  • Applying binary search to unsorted data can produce an incorrect result or miss an existing target.

  • Forgetting that standard binary search needs efficient random access can make its actual runtime O(n).

  • Mixing inclusive [lo, hi] and half-open [lo, hi) conventions causes off-by-one errors.

  • Forgetting that bisect_left and bisect_right return insertion positions, not necessarily the target itself.

  • Python’s list.sort() costs O(n log n) time and O(n) temporary space in the worst case; other sorting algorithms have different space costs. One search on unsorted data may therefore be cheaper than sorting it.

  • Empty input and single-element input should be handled explicitly.

  • Negative numbers and duplicates work correctly as long as the ordering and comparison rules remain consistent.

  • If an array must remain unchanged, do not sort it in place merely to perform binary search.

Interview Tips

Explain why binary search needs sorted input and efficient random access, identify whether the search interval is inclusive, and state both time and auxiliary-space complexity. Interviewers commonly follow up by asking for the first or last duplicate, lower and upper bounds, a rotated-array search, or binary search on a monotonic answer.

4

What data properties determine the best search algorithm?

The best search method is determined by data ordering, key properties, update patterns, and query requirements. Sorted data favors binary search, frequently updated hashable keys often favor a hash table, and data without useful structure can be searched linearly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Data Properties

  • Ordering: Binary search requires sorted data, or a monotonic predicate when searching for an answer rather than an existing element.

  • Key properties: Equality-only searches suit hash tables; comparisons and ordered traversal suit sorted arrays or balanced search trees.

  • Size: Binary search reduces the remaining range geometrically, while linear search may inspect every element.

  • Update frequency: Sorting once is effective for read-heavy data. Frequently inserted or deleted keys may favor a hash table or balanced tree.

  • Query type: Exact match, range, prefix, predecessor, successor, and minimum-feasible-value queries have different optimal structures.

  • Duplicates and stability: First or last occurrence requires special handling. If the original index matters, store each key together with its index.

  • Evaluation cost: Expensive comparisons or feasibility checks favor algorithms that perform fewer evaluations.

  • Memory and locality: Arrays are compact and cache-friendly, while trees and hash tables add storage and pointer overhead.

Complexity and Trade-offs

Approach Best time Average time Worst time Auxiliary space Reason
Linear search O(1) O(n) O(n) O(1) It inspects elements sequentially; the first position is best and the last is worst.
Binary search O(1) O(log n) O(log n) O(1) iterative Each comparison discards half the search interval.
Hash-table lookup O(1) O(1) expected O(n) O(1) Hashing is constant-time on average, but collisions may require many probes.
Balanced-tree lookup O(1) O(log n) O(log n) O(1) iterative A balanced tree has logarithmic height.
Binary search on an answer O(log R) O(log R) O(log R) O(1) iterative Each predicate evaluation halves the candidate range, and finding the threshold needs all log R steps.

Here, n is the number of elements and R is the number of candidate answers. Auxiliary space excludes the input collection; it includes recursion stack space when recursion is used. Recursive binary and tree searches require O(log n) stack space. A hash table or balanced tree also requires O(n) total storage for n entries.

If each feasibility-predicate evaluation costs T, binary search on an answer takes O(T log R) time.

Search Variants and Preconditions

  • Exact search: Standard binary search returns one matching index.

  • Range search: Use a lower bound for the first value at least a key and an upper bound for the first value greater than it. In Python 3.12, these are provided by bisect_left and bisect_right for sorted lists.

  • Duplicate-sensitive search: The lower bound identifies the first occurrence; subtracting one from the upper bound identifies the last occurrence.

  • Rotated sorted array: With distinct values, a modified binary search takes O(log n) time. With duplicates, a straightforward implementation can degrade to O(n) in the worst case.

  • Binary search on an answer: Use a monotonic predicate, commonly a non-decreasing feasibility condition such as “can all items be processed within this capacity?”

  • Implementation convention: An inclusive interval [lo, hi] starts with hi = n - 1 and uses mid = lo + (hi - lo) // 2. The latter avoids overflow in fixed-width languages such as Java and C++, where lo + hi may overflow.

Common Pitfalls and Interview Tips

  • Using binary search on unsorted data produces unpredictable results.

  • Confusing lower-bound and upper-bound definitions causes off-by-one errors.

  • Returning immediately from exact binary search may not return the first or last duplicate.

  • Include sorting, tree maintenance, and hash-table resizing costs when choosing a method.

  • Preserve the input if the caller expects sorting not to mutate it.

  • Test empty input, one element, duplicate values, negative numbers, and already sorted data.

  • Interviewers commonly ask about hash-table collision behavior, balanced-tree height, binary-search boundaries, and when binary search on an answer is valid.

5

Which techniques optimize linear search performance?

Linear-search optimization reduces comparisons or avoids a complete scan through techniques such as early termination, ordered-data pruning, auxiliary indexes, and bidirectional scanning. These approaches improve practical performance, although a single linear search still has a worst-case time complexity of O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Techniques

  • Early termination: Return immediately when the target is found. This improves successful searches but does not help when the target is absent.

  • Ordered-data pruning: If the input is sorted, stop when the current value exceeds the target. Later elements cannot match it.

  • Bidirectional scanning: Search from both ends when the target is likely to be near either end. The worst case remains unchanged.

  • Auxiliary hash index: Build a dictionary mapping values to positions. This supports repeated lookups in average O(1) time at the cost of O(n) preprocessing and space.

  • Self-organizing lists: Move frequently searched elements closer to the front. This can improve skewed access patterns but does not improve the worst case; moving an element in a Python list costs O(n).

  • Sentinel values: In fixed-capacity languages, placing the target beyond the final element can remove repeated bounds checks. In Python, appending to a list may copy it, so this is often slower than a normal loop.

For example, searching [2, 4, 6, 8] for 5 in ascending order:

  1. Compare 2 with 5; continue.

  2. Compare 4 with 5; continue.

  3. Compare 6 with 5; stop because 6 > 5.

  4. Return -1 without inspecting 8.

Complexity and Trade-offs

Approach Best Average Worst Extra space When to use
Plain linear search O(1) O(n) O(n) O(1) One-off, unsorted lookup
Linear search with early exit O(1) O(n) O(n) O(1) Successful one-off searches
Ordered linear search O(1) O(n) O(n) O(1) Sorted data with occasional lookups
Hash index lookup O(1) O(1) O(n) O(n) Many repeated static lookups
Binary search O(1) O(log n) O(log n) O(1) Many lookups on sorted data

These space complexities count auxiliary memory, including any recursion stack, but exclude the input itself. None of these implementations uses recursion. Hash lookups have expected O(1) complexity because Python dictionaries distribute entries across buckets; severe hash collisions can degrade a lookup to O(n).

Binary Search Alternatives

Binary search requires sorted data or a monotonic condition. It performs O(log n) comparisons because each comparison eliminates half of the remaining interval.

  • First occurrence: bisect_left(values, target) returns the lower bound and the first occurrence when the target exists.

  • Last occurrence: bisect_right(values, target) - 1 returns the last matching index.

  • Lower and upper bounds: bisect_left finds the first index whose value is at least the target; bisect_right finds the first index whose value is greater than the target.

  • Rotated sorted array: A modified binary search runs in O(log n) when values are distinct. Duplicate elements can cause the worst case to degrade to O(n).

  • Binary search on an answer: Search a numeric answer range using a monotonic feasibility predicate. It requires O(log R) predicate evaluations for range size R, multiplied by the cost of each evaluation.

Sorting costs O(n log n), so binary search may not be worthwhile for only one lookup.

Common Pitfalls

  • Using binary search on unsorted data produces incorrect results.

  • Confusing lower bound, upper bound, first occurrence, and last occurrence when duplicates exist.

  • Assuming early termination improves unsuccessful searches; an absent target normally requires a full scan.

  • Using a hash index without considering its O(n) space and rebuilding it after the input changes.

  • Mutating the input for sentinels or self-organizing lists when the caller expects it to remain unchanged.

  • Mixing closed intervals [lo, hi] with half-open intervals [lo, hi), causing off-by-one errors.

  • Forgetting that integer overflow remains a concern in fixed-width languages even though it is not an issue in Python.

  • Common interview follow-ups include handling duplicates, choosing between hashing and sorting, and explaining why binary search takes O(log n) time.

7

What limitations does sentinel-based linear search have?

Sentinel-based linear search can remove a per-iteration bounds check by placing a marker after the searchable data, but it remains a linear-search technique rather than a faster asymptotic algorithm. Its main limitations are the need for extra storage, possible mutation of the collection, sentinel ambiguity, and setup overhead that can outweigh the saved check.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A standard linear search checks whether the current element matches the target and whether the index is still within the sequence. A sentinel-based version places a special marker after the searchable elements, allowing the loop to check for the marker instead of performing a separate bounds check on every iteration.

For example, with values [10, 20, 20, 30] and target 20:

  1. Index 0 contains 10, so the search continues.

  2. Index 1 contains 20, so the search returns 1.

If the target is absent, the search examines every real element before reaching the sentinel, which represents failure.

Main Drawbacks

  • No asymptotic improvement: Sentinel search remains O(n) on average and in the worst case. It does not become suitable for large sorted collections when O(log n) binary search is available.

  • Requires extra capacity or storage: The underlying container must have room for the sentinel. A fixed-size, completely full buffer cannot support the technique unless one slot is reserved.

  • Can mutate the original collection: Appending a sentinel temporarily changes the data structure. This is undesirable when the collection is shared, read concurrently, or exposed through an API that guarantees immutability.

  • Requires a distinguishable sentinel: If the sentinel compares equal to the target and its position is not handled separately, an absent target can be reported as a match.

  • Setup can offset the saved check: Resizing a container, appending and removing the sentinel, and adding sentinel-detection logic can cost more than the eliminated bounds check for short searches.

  • Limited benefit in Python: Python’s interpreter overhead generally makes the optimization less attractive than in a low-level language with predictable loop and indexing costs.

  • Applies only to sequential searching: It does not accelerate binary search, tree searches, graph traversal, or searches over immutable sequences unless separate storage is introduced.

Complexity Comparison

Approach Best time Average time Worst time Auxiliary space When to use
Ordinary linear search O(1) O(n) O(n) O(1) Small or unsorted collections
Sentinel linear search O(1) O(n) O(n) O(1) Mutable arrays where bound checks are measurable
Binary search O(1) O(log n) O(log n) O(1) Sorted collections with frequent searches

Linear search examines at most n elements, so its best case is O(1) and its average and worst cases are O(n); the sentinel removes only constant-factor work. Binary search repeatedly halves the remaining search interval, giving O(log n) average and worst-case time and O(1) best-case time when the target is found immediately.

The auxiliary-space figures exclude the input collection itself. All three searches use O(1) auxiliary space and no recursion stack; a sentinel requires one additional O(1) slot or separate element.

Common Pitfalls

  • Allowing the sentinel to equal the target accidentally: This can cause an absent target to be reported as present.

  • Ignoring fixed-capacity constraints: Inserting the sentinel can overflow a buffer or overwrite unrelated data in low-level implementations.

  • Forgetting to restore mutable input: A temporary sentinel should not remain in the caller’s collection.

  • Expecting logarithmic performance: Removing one bounds check does not change O(n) into O(log n).

  • Ignoring edge cases: Empty input should report no match; one-element collections, duplicates, negative numbers, and an already sorted collection must still behave correctly.

8

How do duplicates impact Linear Search performance?

Linear search examines elements sequentially until it finds a match or exhausts the collection. Duplicates do not change its asymptotic time complexity, but the position of the first matching element determines how quickly a first-match search terminates.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Effect of Duplicates

  • Finding the first occurrence: The search stops at the first matching element. Additional copies later in the collection are never examined.

  • Finding any occurrence: The first match also ends the search, so later duplicates have no effect on its running time.

  • Finding all occurrences: The algorithm must scan the entire collection and record every match. If there are k matches, the output occupies O(k) space.

  • Target absent: Every element is checked, regardless of how many duplicate values the collection contains.

  • No quadratic penalty: Each element is compared with the target once per scan. Duplicate values do not require additional comparisons with each other.

For example, searching for 3 in [7, 3, 3, 3, 8] proceeds as follows:

  1. Compare 7 with 3; no match.

  2. Compare the first 3 with 3; return index 1.

  3. The remaining duplicates are not examined.

Complexity

Search scenario Best Average Worst Working space
Find first occurrence O(1) O(n) O(n) O(1)
Find any matching occurrence O(1) O(n) O(n) O(1)
Find all occurrences O(n) O(n) O(n) O(1), plus O(k) for results

The average case is O(n) under the standard assumption that a successful target is equally likely to occupy any position; the expected number of comparisons is then approximately n / 2. An unsuccessful search always requires O(n) comparisons. Space is measured excluding the input collection, and there is no recursion stack.

Linear Search Compared with Binary Search

Approach Time Space Requirement
Linear search O(1) best; O(n) average and worst O(1) Works on unsorted or sorted data
Binary search O(1) best; O(log n) average and worst O(1) Requires sorted data or another suitable monotonic condition

For sorted data containing duplicates, bisect_left finds the first index where the target could be inserted, while bisect_right finds the position after all equal values. Thus, bisect_right(values, target) - 1 gives the last matching index when the target exists.

Common Pitfalls

  • Do not claim duplicates make linear search O(n²); each element is still compared only once per scan.

  • Do not assume duplicate values guarantee an early exit; the first matching position controls termination.

  • To find every occurrence, continue scanning after the first match and account for O(k) output space.

  • Use binary search only when the data is sorted or the search condition supports a monotonic boundary.

  • An empty collection requires no comparisons, while a one-element collection requires at most one comparison. Negative values and duplicate values require no special handling, and sorting the input does not improve linear search asymptotically.

9

How do you implement order-agnostic linear search in Python?

An order-agnostic linear search checks elements sequentially, so it works on both sorted and unsorted input. It returns the index of the first matching element or None when the target is absent.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Start at index 0 and compare each element with the target.

  • Return immediately when a match is found.

  • If every element is checked without a match, return None.

  • Do not stop early because the current element is greater than the target; that is only safe for sorted input.

  • With duplicates, this implementation returns the first matching index.

Complexity

  • Best case: O(1) when the first element matches.

  • Average case: O(n) when the target is equally likely to occupy any position; roughly half the elements are examined on average.

  • Worst case: O(n) when the target is last or absent.

  • Auxiliary space: O(1), including the constant-size call stack. The input sequence is not counted.

Here, n is the number of elements.

Linear Search vs. Binary Search

Approach Time Space Requirement When to use
Order-agnostic linear search O(n) O(1) No ordering requirement Input may be unsorted
Binary search O(log n) O(1) Sorted data or a monotonic condition Large, repeatedly searched sorted data

For ascending sorted Python lists, bisect_left finds the lower bound—the first position whose value is at least the target—while bisect_right finds the upper bound—the first position whose value is greater than the target. Together, they delimit all occurrences, allowing the first occurrence to be found with bisect_left and the last with bisect_right - 1.

Related binary-search variants include:

  • Rotated sorted array: Use a custom binary search that accounts for the rotation, taking O(log n) time. The standard bisect functions cannot search such an array directly.

  • Binary search on the answer: Search a candidate interval using a monotonic feasibility predicate, taking O(log R) predicate evaluations for R candidates.

Code Example

from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")


def order_agnostic_linear_search(values: Sequence[T], target: T) -> int | None:
    """Return the first index of target, or None if it is absent."""
    for index, value in enumerate(values):
        if value == target:
            return index
    return None


# Unsorted input; target is found at index 2.
print(order_agnostic_linear_search([8, 3, 12, 3, 5], 12))  # 2

Example Walkthrough

For values = [8, 3, 12, 3, 5] and target = 12:

  1. Index 0: compare 8 with 12; no match.

  2. Index 1: compare 3 with 12; no match.

  3. Index 2: compare 12 with 12; match.

  4. Return 2 without examining the remaining elements.

The same steps apply if the input is already sorted.

Common Pitfalls

  • Empty input: The function correctly returns None.

  • Single element: It returns 0 for a match and None otherwise.

  • Duplicates: The implementation returns the first occurrence.

  • Negative numbers: They are handled correctly without special-case logic.

  • Already sorted input: The function still performs a linear scan; sorting does not change this implementation’s O(n) complexity.

  • Absent target: The function returns None after scanning all n elements.

  • Premature termination: Do not stop when value > target unless the sequence is known to be sorted.

  • Mutating input: The implementation leaves the input unchanged.

  • Unnecessary recursion: Iteration avoids recursion-depth issues and uses constant auxiliary space.

  • Equality semantics: Python considers values such as True and 1 equal because True == 1; use domain-specific keys when that distinction matters.

10

How do I perform linear search on a multidimensional array?

Linear search on a multidimensional Python list checks each scalar element in depth-first order until it finds the target. The implementation below returns the tuple of indices identifying the target’s location.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Treat each nested list as another dimension to explore.

  • Compare each scalar element with the target.

  • When an element is a list, descend into it and record the index used to reach it.

  • Return a path such as (1, 2), meaning the element at row 1 and column 2.

  • Use an explicit stack instead of recursion so deeply nested data cannot exceed Python’s recursion limit.

  • Track active ancestor lists to avoid infinite traversal if cyclic references occur.

The algorithm does not modify the input.

Complexity

Let N be the total number of stored positions and scalar values inspected, and let D be the maximum nesting depth.

Case Time Reason
Best O(1) The target is the first value examined.
Average O(N) A randomly positioned present target requires examining roughly half the values on average.
Worst O(N) The target is absent or appears last, so every value is examined.
  • Auxiliary space: O(D), including the explicit traversal stack, index path, and active-list IDs.

  • Input space: O(N) for the multidimensional array itself; input is not counted as auxiliary space.

  • For a flat list, D = 1, so auxiliary space is O(1).

  • These bounds assume an O(1) target-equality comparison, as with ordinary scalar values.

For unstructured multidimensional data, linear search is asymptotically optimal in the worst case: if the target is absent, every value may need inspection to prove absence.

Binary Search Alternatives

Binary search requires globally sorted data or a monotonic condition; it cannot be applied directly to an arbitrary multidimensional array.

  • Sorted rows: Search each sorted row independently. For R rows and C columns, this takes O(R log C) time.

  • Flattened sorted data: Flattening takes O(N) time and space; afterward, each binary search takes O(log N). If the source is not globally sorted, sorting adds O(N log N) time, making the end-to-end operation O(N log N).

  • Lower and upper bounds: On a flattened sorted list, bisect_left finds the first position greater than or equal to a value, while bisect_right finds the first position greater than it.

  • First occurrence: Use bisect_left, then verify that the selected element equals the target.

  • Last occurrence: Use bisect_right(...) - 1, then verify that the selected element equals the target.

  • Rotated sorted array: Identify the rotation pivot and binary-search the appropriate half.

  • Binary search on the answer: Search for the smallest capacity, distance, or square root satisfying a monotonic predicate.

Code Example

def linear_search_multidimensional(
    data: list[object],
    target: object,
) -> tuple[int, ...] | None:
    """Return the first DFS path to a scalar target, or None."""
    # Each frame stores a list and the index of its next value to inspect.
    stack: list[tuple[list[object], int]] = [(data, 0)]

    # Indices leading to the list currently being examined.
    path: list[int] = []

    # IDs of lists on the active path, used to detect cyclic references.
    active_list_ids: set[int] = {id(data)}

    while stack:
        current_list, index = stack[-1]

        if index == len(current_list):
            stack.pop()
            active_list_ids.discard(id(current_list))
            if path:
                path.pop()
            continue

        stack[-1] = (current_list, index + 1)
        value = current_list[index]

        # Search scalar leaves; assume equality takes O(1) time.
        if not isinstance(value, list) and value == target:
            return tuple(path + [index])

        if isinstance(value, list):
            child_id = id(value)
            if child_id not in active_list_ids:
                path.append(index)
                stack.append((value, 0))
                active_list_ids.add(child_id)

    return None


matrix = [[5, 8], [2, 9]]
print(linear_search_multidimensional(matrix, 9))  # (1, 1)

Example walkthrough:

  1. The root element at index 0 is [5, 8], so the search descends into it.

  2. It compares 5 and 8 with 9; neither matches.

  3. The root element at index 1 is [2, 9], so the search descends into it.

  4. It compares 2, then 9, and returns the path (1, 1).

Common Pitfalls

  • Empty input: The function immediately returns None.

  • One element: A one-element list is handled by the same loop.

  • Duplicates: The function returns the first depth-first match. For a rectangular matrix and scalar target, this is row-major order; irregular nesting can produce a different order.

  • Negative values: Ordinary equality checks work without special handling.

  • Already sorted input: Sorting does not change the worst-case complexity of linear search.

  • Unequal dimensions: Jagged nested lists are supported when every dimension is represented by a Python list.

  • Cycles: A child pointing to an active ancestor is skipped, preventing an infinite loop.

  • Mutating input: Do not remove elements or modify the nested lists during traversal; this implementation leaves the input unchanged.

  • Common follow-up: Interviewers may ask how to return all matches, count matches, or enforce a particular traversal order.

11

Why is binary search complexity O(log n)?

Binary search runs in O(log n) because each comparison eliminates approximately half of the remaining search space. Unlike linear search, it repeatedly divides the candidate range rather than inspecting elements one by one.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Binary search requires either:

  • A sorted collection, so comparisons can consistently eliminate one half.

  • A monotonic predicate over a numeric range, such as “is the required capacity at least x?”

Using an exclusive upper bound, the active interval is [lo, hi). The midpoint is:

mid = lo + (hi - lo) // 2

This midpoint formula avoids integer overflow in languages where lo + hi could exceed the maximum integer value.

For values = [2, 5, 8, 12, 16] and target = 12:

  1. [0, 5): mid = 2, value 8; the target is larger, so search [3, 5).

  2. [3, 5): mid = 4, value 16; the target is smaller, so search [3, 4).

  3. [3, 4): mid = 3, value 12; the target is found.

Complexity

After k comparisons, the remaining candidate count is at most:

[ leftlceil frac{n}{2^k} rightrceil ]

The search finishes when this reaches one. Therefore:

[ 2^k ge n quadRightarrowquad k ge log_2 n ]

Case Time Reason
Best O(1) The target is found at the first midpoint.
Average O(log n) The search repeatedly halves the candidate range.
Worst O(log n) Even an unsuccessful search reduces the range by half each iteration.

An iterative implementation uses O(1) auxiliary space, excluding the input. A recursive implementation uses O(log n) space because each recursive call remains on the call stack.

Approach Time Space When to use
Linear search O(n) O(1) Unsorted data or only a few searches
Binary search O(log n) O(1) Sorted data or a monotonic search condition

Common Variants

Variant Approach
Exact match Check whether the midpoint equals the target.
First occurrence Continue left after finding an equal value.
Last occurrence Continue right after finding an equal value.
Lower bound Find the first index whose value is at least the target.
Upper bound Find the first index whose value is greater than the target.
Rotated sorted array Determine which half is sorted, then discard the impossible half.
Binary search on the answer Binary-search a numeric range using a monotonic feasibility predicate.

Python provides bisect_left and bisect_right for lower and upper bounds. Rotated-array binary search generally assumes distinct values; handling duplicates can degrade to O(n). Binary search on the answer requires O(log U) predicate evaluations for search range U; if each predicate evaluation costs O(n), total time is O(n log U).

Common Pitfalls

  • Unsorted input: Ordinary binary search gives incorrect results unless the data is sorted or a monotonic condition is available.

  • Wrong interval convention: Mixing inclusive and exclusive bounds commonly causes off-by-one errors.

  • Duplicate values: Exact search may return any matching index; use first-occurrence or last-occurrence logic when the specific match matters.

  • Empty input: A standard implementation can return -1 immediately without indexing the collection.

  • Negative values and one-element lists: These are handled normally.

  • Rotated arrays with duplicates: Ambiguous ordering can force linear scanning.

  • Overflow in other languages: Prefer lo + (hi - lo) // 2 over lo + hi.

  • Typical follow-up questions: Interviewers commonly ask about lower versus upper bounds, searching without a sorted array, choosing a search range, or implementing binary search recursively.

12

How do recursive and iterative binary searches differ?

Recursive binary search calls itself on a smaller search interval, while iterative binary search updates the interval boundaries in a loop. Both use the same divide-and-conquer strategy; their main differences are control flow, stack usage, and function-call overhead.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Binary Search Works

Binary search maintains an inclusive interval [lo, hi] over data sorted in ascending order:

  1. Calculate the midpoint as mid = lo + (hi - lo) // 2.

  2. Compare the value at mid with the target.

  3. Discard the half that cannot contain the target.

  4. Continue until the target is found or lo > hi.

The midpoint formula avoids overflowing the addition in (lo + hi) // 2 in fixed-width languages such as Java or C++, provided the indexes are valid and non-negative. Python integers do not overflow, but the same formula remains portable.

For [1, 3, 3, 5, 7] searching for 7:

Step Interval Midpoint Value Result
1 [0, 4] 2 3 Target is larger; use [3, 4]
2 [3, 4] 3 5 Target is larger; use [4, 4]
3 [4, 4] 4 7 Found at index 4

Recursive vs. Iterative

Aspect Recursive Iterative
Control flow Each recursive call handles one smaller interval A loop handles each smaller interval
Stack usage Uses the call stack Uses no recursion stack
Readability Naturally expresses the recursive structure Often clearer for interval-based searches
Overhead Has function-call overhead Usually has slightly less overhead
Recursion limit Uses the runtime call stack and is subject to its limits in principle Has no recursion-limit concern
Typical use Teaching divide-and-conquer logic Production searches and large inputs

For binary search, recursion depth is only O(log n), so it is generally shallow for ordinary searchable collections.

Boundary and Related Variants

  • Lower bound: In Python 3.12, bisect_left(values, target) returns the first index whose value is greater than or equal to target.

  • Upper bound: bisect_right(values, target) returns the first index whose value is greater than target.

  • First occurrence: Find bisect_left(values, target), then verify that the index is valid and the value matches.

  • Last occurrence: Find bisect_right(values, target) - 1, then verify that the index is valid and the value matches.

  • Rotated sorted array: Determine which half is sorted and whether the target lies within that half. The standard approach is O(log n) for distinct elements; duplicates can make some implementations degrade to O(n).

  • Binary search on the answer: Search a numerical range for the smallest value satisfying a monotonic predicate, such as minimum shipping capacity. It takes O(log R) time for range size R when each predicate check is O(1); if a check costs O(p), the total is O(p log R).

Complexity

  • Time, best case: O(1) for both implementations because the midpoint may immediately match.

  • Time, average case: O(log n) because each comparison approximately halves the remaining search space.

  • Time, worst case: O(log n) for both implementations because the interval may halve on every iteration until it becomes empty.

  • Recursive auxiliary space, best case: O(1) when the target is found at the first midpoint.

  • Recursive auxiliary space, average and worst cases: O(log n) because the recursion stack can contain O(log n) calls.

  • Iterative auxiliary space: O(1) in the best, average, and worst cases because only a fixed number of variables are maintained.

  • These space complexities count auxiliary memory, including the recursion stack where applicable, but do not count the input collection itself.

Common Pitfalls

  • Unsorted input: Ordinary binary search gives incorrect results unless the search predicate is monotonic.

  • Off-by-one errors: Clearly choose either an inclusive [lo, hi] interval or a half-open [lo, hi) interval and use it consistently.

  • Duplicate values: A basic search does not guarantee the first or last matching index; use the boundary variants when that matters.

  • Empty input: A search should report that the target is absent.

  • One element: Return the only index when it matches; otherwise report that the target is absent.

  • Negative values: Binary search handles negative values normally; sorting order rather than sign determines their positions.

  • Already sorted input: No sorting is needed, and the input can be searched immediately.

  • Overflow: Prefer lo + (hi - lo) // 2 over (lo + hi) // 2 in fixed-width languages.

  • Common follow-up: Interviewers often ask about first or last occurrence, lower and upper bounds, rotated arrays, or binary search on the answer.

13

Why does binary search round down the midpoint?

Floor division keeps the midpoint strictly inside the active half-open interval [lo, hi), guaranteeing that each comparison reduces the search space. Rounding up can produce mid == hi; with an update such as hi = mid, the interval would not shrink and the loop could run forever.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Round Down?

For lo < hi, the expression mid = lo + (hi - lo) // 2 guarantees lo <= mid < hi. Flooring is particularly convenient for lower-bound searches over [lo, hi).

Rounding up is not inherently incorrect, but it requires different interval boundaries and carefully chosen updates. The lo + (hi - lo) // 2 form also avoids overflowing lo + hi in fixed-width languages such as Java or C++, where adding two large indices directly can exceed the maximum integer value.

How the Search Shrinks

The algorithm repeatedly compares the target with the midpoint and discards the half that cannot contain the answer:

  • If values[mid] < target, set lo = mid + 1.

  • Otherwise, set hi = mid.

  • Stop when lo == hi.

For example, searching for 2 in [1, 2, 2, 4] proceeds as follows:

Active interval Midpoint Comparison Next interval
[0, 4) 2 2 < 2 is false [0, 2)
[0, 2) 1 2 < 2 is false [0, 1)
[0, 1) 0 1 < 2 is true [1, 1)

The lower-bound result is index 1, the first position whose value is at least 2.

Binary Search Variants

  • Lower bound: Returns the first index where the value is greater than or equal to the target. Python provides bisect_left.

  • Upper bound: Returns the first index where the value is greater than the target. Python provides bisect_right.

  • First occurrence: Use the lower bound and verify that the value at that index equals the target.

  • Last occurrence: Subtract one from the upper bound and verify the value.

  • Rotated sorted array: Determine which half is sorted, then check whether the target lies within that half. With distinct values, the complexity is logarithmic; duplicates can force linear behavior.

  • Binary search on an answer: Search for the smallest value satisfying a monotonic predicate. For example, “minimum capacity” can use a predicate such as total_load <= capacity. If evaluating the predicate costs P and the candidate range has size U, the worst-case time is O(P log U).

Complexity

Approach Best Time Average Time Worst Time Auxiliary Space Use When
Linear search O(1) O(n) O(n) O(1) Data is unsorted
Binary search O(1) O(log n) O(log n) O(1) Data is sorted or the condition is monotonic

Binary search takes O(log n) because each comparison eliminates approximately half of the remaining interval; its best case ends immediately when the first midpoint matches the target. Linear search takes O(n) in the average and worst cases because it may inspect every element; its best case is O(1) when the first element matches.

These space figures exclude the input itself. An iterative implementation uses O(1) auxiliary space; a recursive implementation uses O(log n) space for the recursion stack. Searching a rotated array containing duplicates has O(n) worst-case time because many elements may need to be skipped.

Common Pitfalls

  • Mixing inclusive [lo, hi] and half-open [lo, hi) boundaries causes off-by-one errors.

  • Rounding up with hi = mid can leave the interval unchanged.

  • Binary search requires sorted data or a monotonic predicate.

  • Rotated-array search with duplicates has O(n) worst-case time.

  • Handle empty input, one element, duplicates, and negative targets explicitly.

  • In interviews, expect follow-ups about lower versus upper bounds, finding both first and last occurrences, and searching a monotonic answer space.

15

How do you binary search objects sorted by a key?

Binary search repeatedly halves a sorted collection by comparing the target key with the key of the middle object. It works with any object that exposes a comparable key, provided the collection is already sorted in the same key order used by the search.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Maintain two indexes, left and right, representing the half-open search interval [left, right).

  • Calculate the midpoint as left + (right - left) // 2. This avoids integer overflow in languages such as Java or C++ when left + right could exceed the maximum integer value.

  • Extract the middle object’s key and compare it with the target:

  • If the middle key is smaller, set left = mid + 1.

  • If it is larger, set right = mid.

  • If they match, return the object’s index.

  • If the interval becomes empty, the target is absent.

For example, search for price 30 in keys [10, 20, 25, 40]:

  1. [0, 4): mid = 2, key 25 is too small, so search [3, 4).

  2. [3, 4): mid = 3, key 40 is too large, so search [3, 3).

  3. [3, 3): the interval is empty, so return -1.

Comparison With Linear Search

Approach Best time Average time Worst time Auxiliary space When to use
Linear search O(1) O(n) O(n) O(1) Unsorted data or very small collections
Binary search O(1) O(log n) O(log n) O(1) Data already sorted by the search key

Binary search assumes each comparison discards half of the remaining candidates.

Variants and Extensions

  • Lower bound: bisect_left returns the first index whose key is greater than or equal to the target.

  • Upper bound: bisect_right returns the first index whose key is greater than the target.

  • First occurrence: Use the lower bound and verify that its key equals the target; otherwise, the target is absent.

  • Last occurrence: If the target exists, its last occurrence is at bisect_right(...) - 1. The interval between the lower and upper bounds contains all matching objects.

  • Rotated sorted array: Modify the comparison logic to account for the rotation. The predictable O(log n) version generally assumes distinct keys.

  • Binary search on the answer: Search a numerical range using a monotonic predicate, such as whether capacity c can ship all packages within d days.

  • Descending order: Reverse the comparison operators or use a corresponding descending comparator.

In Python 3.12, bisect_left and bisect_right support a key callable for sorted lists of objects.

Code Example

from collections.abc import Callable, Sequence
from dataclasses import dataclass
from typing import TypeVar

T = TypeVar("T")
K = TypeVar("K")


@dataclass(frozen=True)
class Product:
    sku: str
    price: int


def binary_search_by_key(
    items: Sequence[T],
    target_key: K,
    key: Callable[[T], K],
) -> int:
    """Return the index of a matching key, or -1 when it is absent."""
    left, right = 0, len(items)

    while left < right:
        mid = left + (right - left) // 2
        middle_key = key(items[mid])

        if middle_key < target_key:
            left = mid + 1
        elif middle_key > target_key:
            right = mid
        else:
            return mid

    return -1


products = [
    Product("A-100", 10),
    Product("B-200", 20),
    Product("C-300", 25),
    Product("D-400", 40),
]

index = binary_search_by_key(
    products,
    25,
    key=lambda product: product.price,
)
print(index)  # Expected output: 2

Complexity

  • Time: O(1) best case, O(log n) average case, and O(log n) worst case, assuming key extraction and comparison are O(1).

  • Auxiliary space: O(1); the input collection is not counted.

  • If key extraction and comparison cost O©, the best case costs O© and the worst case costs O(c log n).

  • Sorting the objects initially costs O(n log n) with a comparison-based sort, but that cost is outside the search operation.

Common Pitfalls

  • Incorrect ordering: The key used for sorting must match the key and direction used for searching.

  • Inclusive or exclusive bounds: This implementation uses [left, right); mixing conventions commonly causes off-by-one errors.

  • Duplicate keys: The basic algorithm may return any matching object. Use lower and upper bounds when the first or last occurrence matters.

  • Mutable input: Changing keys during the search can invalidate the sorted-order assumption.

  • Type mismatches: Keys must have a consistent, supported ordering; comparisons between incompatible types can raise TypeError.

  • Edge cases: Empty input returns -1, a one-element input works, negative numeric keys are supported, and already sorted input is required by the algorithm.

16

How do you perform binary search in a rotated sorted array?

Use a modified binary search that identifies which half of the current interval is sorted before deciding which direction to search. This works when the array was originally sorted in non-decreasing order and then rotated at an unknown pivot.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

At each step, the interval [left, right] is inclusive. Calculate the midpoint using:

mid = left + (right - left) // 2

This form avoids overflow in languages with fixed-width integers, although Python integers do not overflow.

  1. If nums[mid] == target, return mid.

  2. If nums[left] == nums[mid] == nums[right], duplicates prevent identifying a sorted half. Remove both endpoints and continue.

  3. Otherwise, determine the sorted half:

  4. If nums[left] <= nums[mid], the left half is sorted.

  5. Otherwise, the right half is sorted.

  6. Check whether the target lies within that sorted half and discard the half that cannot contain it.

The algorithm returns the index of the target, or -1 if it is absent.

Complexity

Approach Best time Average time Worst time Auxiliary space
Linear search O(1) O(n) O(n) O(1)
Modified binary search, distinct values O(1) O(log n) O(log n) O(1)
Modified binary search, duplicates allowed O(1) O(log n) on ordinary inputs O(n) O(1)
  • With distinct values, every iteration discards approximately half of the remaining interval.

  • With duplicates, equal boundary and midpoint values may force the algorithm to shrink the interval one element at a time.

  • Space complexity is O(1) auxiliary space. The input array is not counted, and no recursion stack is used.

Code Example

def binary_search_rotated(nums: list[int], target: int) -> int:
    """Return target's index in a rotated sorted array, or -1 if absent."""
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Duplicates make it impossible to identify the sorted half.
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
            continue

        if nums[left] <= nums[mid]:
            # The left half is sorted.
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # The right half is sorted.
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1


if __name__ == "__main__":
    values = [4, 5, 6, 7, 0, 1, 2]
    print(binary_search_rotated(values, 0))  # 4
    print(binary_search_rotated(values, 3))  # -1

Walkthrough

For nums = [4, 5, 6, 7, 0, 1, 2] and target = 0:

  1. The interval is [0, 6]; mid = 3 and nums[3] = 7.

  2. The left half [4, 5, 6, 7] is sorted, and 0 is outside it. Set left = 4.

  3. The interval is [4, 6]; mid = 5 and nums[5] = 1.

  4. The left half [0, 1] is sorted, and 0 lies within it. Set right = 4.

  5. The interval is [4, 4]; nums[4] == 0, so return 4.

Related Search Variants

Variant Standard approach Important requirement
First occurrence Use bisect_left on a sorted list The list must be sorted
Last occurrence Use bisect_right(...) - 1 The list must be sorted
Lower bound bisect_left(values, target) First index whose value is at least target
Upper bound bisect_right(values, target) First index whose value is greater than target
Rotated sorted array Modified binary search as above The array must be a rotation of a sorted array
Binary search on an answer Search a monotonic feasibility condition For example, find minimum capacity with a valid predicate

Common Pitfalls

  • Incorrect interval convention: This implementation uses an inclusive [left, right] interval.

  • Off-by-one errors: Use mid - 1 and mid + 1 carefully when discarding halves.

  • Ignoring duplicates: If boundary and midpoint values are equal, the sorted half may be ambiguous.

  • Assuming arbitrary input is valid: The guarantee that the array is a rotated sorted array is essential.

  • Overflow in other languages: Prefer left + (right - left) // 2 over (left + right) // 2.

  • Edge cases: Empty input returns -1; one-element arrays work naturally; negative values are supported; an already sorted array is handled as a rotation with the pivot at the end.

  • Graph-specific issues such as disconnected graphs, cycles, and visited sets do not apply to this array-search algorithm.

Interviewers commonly follow up by asking how duplicates affect the complexity, whether the algorithm can return a value instead of an index, or how to prove that each discarded half cannot contain the target.

17

How do you search a virtually infinite sorted array?

Use exponential search to discover an upper bound, then perform binary search within that range. This avoids scanning an array whose length is unknown or extremely large.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm assumes:

  • Indices are non-negative and support random access.

  • Values are sorted in non-decreasing order.

  • Values eventually grow above the target, or the array has a finite size or upper sentinel. Otherwise, an absent target cannot always be detected.

  • Check index 0 for an immediate match.

  • Inspect indices 1, 2, 4, 8, ... until the inspected value is at least the target.

  • Binary-search the discovered range using the inclusive interval [lo, hi].

  • Return a matching index, or -1 when absence can be determined from the available bounds.

For target 9 in A[i] = 2*i + 1:

Step Bounds Value Action
Expand [0, 1] A[1] = 3 3 < 9, expand
Expand [2, 2] A[2] = 5 5 < 9, expand
Expand [3, 4] A[4] = 9 Upper bound found
Binary [3, 4] A[3] = 7 Continue with [4, 4]
Binary [4, 4] A[4] = 9 Return 4

Search Variants

  • Linear search: Checks elements sequentially, works on unsorted data, and takes O(n) time.

  • Binary search: Requires sorted data or a monotonic predicate and takes O(log N) time when the bounds are known.

  • Lower bound: bisect_left finds the first index whose value is at least the target.

  • Upper bound: bisect_right finds the first index whose value is greater than the target.

  • First occurrence: Apply lower-bound logic and verify that the value equals the target.

  • Last occurrence: Apply upper-bound logic, subtract one, and verify equality.

  • Rotated sorted array: Identify the sorted half, discard the half that cannot contain the target, and repeat in O(log N) time.

  • Binary search on the answer: Search a monotonic numeric domain, such as minimum shipping capacity. For a domain of size R, this takes O(log R) time.

Complexity

Let N be the finite array length or the number of positions in the range needed to establish an upper bound.

Approach Best time Average time Worst time Auxiliary space
Linear search O(1) O(n) O(n) O(1)
Binary search with known bounds O(1) O(log N) O(log N) O(1)
Exponential plus binary search O(1) O(log N) O(log N) O(1)

For a target at index k, both phases together take O(log(k + 1)) comparisons. Space is O(1), including the recursion stack; the input is not counted.

Code Example

from typing import Protocol


class SortedSearchArray(Protocol):
    def __getitem__(self, index: int) -> int:
        """Return the value at a non-negative index."""

    def size(self) -> int | None:
        """Return a finite length, or None for an unbounded virtual array."""


class VirtualArray:
    """An infinite, increasing arithmetic progression with random access."""

    def __init__(self, start: int = 1, step: int = 2) -> None:
        if step <= 0:
            raise ValueError("step must be positive")
        self.start = start
        self.step = step

    def __getitem__(self, index: int) -> int:
        if index < 0:
            raise IndexError("VirtualArray indices must be non-negative")
        return self.start + index * self.step

    def size(self) -> int | None:
        return None


def find_element(array: SortedSearchArray, target: int) -> int:
    """Return an index of target, or -1 when absence can be determined."""
    size = array.size()
    if size is not None and size < 0:
        raise ValueError("array size cannot be negative")
    if size == 0:
        return -1

    first_value = array[0]
    if first_value == target:
        return 0
    if size == 1:
        return -1

    lo = 0
    hi = 1

    # Exponential search establishes an inclusive upper bound.
    while True:
        if size is not None and hi >= size:
            hi = size - 1
            break

        value = array[hi]
        if value >= target:
            break

        lo = hi + 1
        hi *= 2

    # Binary search over the inclusive interval [lo, hi].
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        value = array[mid]

        if value == target:
            return mid
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1


example = VirtualArray()
print(find_element(example, 9))  # 4

Best Practices

  • Use mid = lo + (hi - lo) // 2 to avoid overflow in fixed-width integer languages. Python integers do not overflow.

  • In fixed-width languages, check that hi *= 2 cannot overflow.

  • For a finite array, cap the exponential expansion at its final valid index.

  • If the first or last duplicate matters, use lower-bound or upper-bound logic rather than returning an arbitrary match.

  • Do not sort an already sorted array or mutate the input.

Common Pitfalls

  • Incorrect bounds: The implementation uses [lo, hi]; changing it to [lo, hi) requires adjusting the comparisons.

  • Infinite expansion: A bounded-above sequence without a sentinel can expand forever when the target exceeds every value.

  • Duplicate handling: The implementation returns one matching index, not necessarily the first or last.

  • Edge cases: The code handles empty input, one-element arrays, negative targets, and already sorted input. Graph concerns such as disconnected graphs, cycles, and visited sets do not apply.

  • Interview follow-up: Interviewers commonly ask about first or last occurrence, detecting an absent target, and adapting the algorithm to a finite array.

18

How does interpolation search work on sorted data?

Interpolation search estimates a target’s position by using the values at the current search boundaries. On uniformly distributed, sorted data, it can outperform binary search, but its worst case is still O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an ascending sorted array, interpolation search estimates where the target should be using proportional distance rather than always selecting the middle element:

[ position = low + frac{(target - values[low])(high - low)}{values[high] - values[low]} ]

The formula is applied to the current interval [low, high]:

  1. Calculate position using the endpoint values.

  2. If values[position] equals the target, return that index.

  3. If the target is smaller, set high = position - 1.

  4. Otherwise, set low = position + 1.

  5. Stop when the interval becomes empty.

Unlike binary search, interpolation search does not necessarily halve the remaining interval. Its performance depends heavily on the distribution of values.

Complexity and Comparisons

Approach Best time Average time Worst time Space When to use
Linear search O(1) O(n) O(n) O(1) auxiliary Small or unsorted collections
Binary search O(1) O(log n) O(log n) O(1) auxiliary Any sorted collection
Interpolation search O(1) O(log log n) O(n) O(1) auxiliary Sorted, approximately uniform data

The O(log log n) average case for interpolation search assumes values are uniformly distributed. Highly clustered or irregular values can make each estimate eliminate only a small portion of the interval, producing O(n) worst-case behavior.

The space complexity is O(1) auxiliary, including the recursion stack because the implementation is iterative. The input array occupies O(n) space but is not counted as additional space.

Search Variants

Interpolation search has related lower-bound forms:

  • First occurrence: Use a lower-bound search that finds the first element greater than or equal to the target.

  • Last occurrence: Use an upper-bound search that finds the first element greater than the target, then subtract one.

  • Lower and upper bounds: In Python, bisect_left and bisect_right provide predictable binary-search implementations.

  • Rotated sorted array: First locate the rotation pivot with binary search, then search the applicable segment.

  • Search on the answer: Use binary search over a numeric range when a monotonic predicate determines feasibility.

For predictable performance and straightforward duplicate handling, Python’s bisect_left and bisect_right are usually preferable to a custom interpolation implementation.

Example Trace

Search for 100 in [10, 20, 30, 40, 100, 200]:

  1. The initial interval is [0, 5].

  2. The estimate is 0 + ((100 - 10) × 5) // (200 - 10) = 2.

  3. values[2] is 30, which is smaller than 100.

  4. The next interval is [3, 5].

  5. The estimate is 3 + ((100 - 40) × 2) // (200 - 40) = 3.

  6. values[3] is 40, which is smaller than 100.

  7. The next interval is [4, 5].

  8. The estimate is 4 + ((100 - 100) × 1) // (200 - 100) = 4.

  9. values[4] is 100, so the algorithm returns index 4.

Code Example

from collections.abc import Sequence


def interpolation_search(values: Sequence[int], target: int) -> int:
    """Return an index of target in ascending sorted values, or -1 if absent."""
    low = 0
    high = len(values) - 1

    while low <= high:
        # This also handles an empty array and a one-element interval.
        if values[low] == values[high]:
            return low if target == values[low] else -1

        if target < values[low] or target > values[high]:
            return -1

        position = low + (
            (target - values[low]) * (high - low)
        ) // (values[high] - values[low])

        if values[position] == target:
            return position
        elif target < values[position]:
            high = position - 1
        else:
            low = position + 1

    return -1


print(interpolation_search([10, 20, 30, 40, 100, 200], 100))  # 4

Common Pitfalls and Interview Tips

  • Unsorted input: The algorithm assumes ascending order unless a monotonic ordering can otherwise justify the estimates.

  • Duplicate values: This implementation returns one matching index, not necessarily the first or last occurrence.

  • Off-by-one errors: Maintain an inclusive [low, high] interval and test it before accessing either endpoint.

  • Integer overflow: In Java or C++, the intermediate multiplication may overflow a small fixed-width integer; use a sufficiently wide numeric type.

  • Negative numbers: The formula works with negative values when the array is sorted and the denominator is positive.

  • Distribution assumptions: Always state that O(log log n) average time assumes approximately uniform data.

  • Common follow-up: Interviewers may ask how to find the first occurrence, compare it with binary search, or explain why skewed distributions cause O(n) behavior.

20

How does Jump Search work on sorted arrays?

Jump Search, also called Block Search, finds a target in a sorted array by skipping fixed-size blocks and linearly searching only the block that may contain the target. Using a block size of approximately (sqrt{n}), it performs (O(sqrt{n})) comparisons and requires (O(1)) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Jump Search divides a sorted array into blocks of approximately (sqrt{n}) elements:

  1. Choose the block size as floor(sqrt(n)).

  2. Compare the target with the last element of the current block.

  3. If that element is smaller than the target, skip the entire block.

  4. Otherwise, scan the current block sequentially.

  5. If every relevant block is skipped, return “not found.”

The array must be sorted in ascending order. Unlike binary search, Jump Search does not repeatedly divide the remaining range in half.

For [-5, 1, 3, 3, 7, 9, 12] with block size 2:

  • Block [-5, 1]: its last element, 1, is smaller than 7; skip it.

  • Block [3, 3]: its last element, 3, is smaller than 7; skip it.

  • Block [7, 9]: its last element, 9, is at least 7; scan it.

  • The scan finds 7 at index 4.

Complexity

For block size (m), the algorithm performs approximately (n/m) block-boundary comparisons and scans at most (m) elements.

  • Best case: (O(1)), when the target is the first element.

  • Average case: (O(sqrt{n})), because (n/m + m) is minimized when (m approx sqrt{n}).

  • Worst case: (O(sqrt{n})), including scanning the final candidate block.

  • Auxiliary space: (O(1)). The input array is not counted; including the stored input, total space is (O(n)). There is no recursion stack.

Comparison With Linear and Binary Search

Approach Best time Average time Worst time Auxiliary space When to use
Linear Search (O(1)) (O(n)) (O(n)) (O(1)) Unsorted data or a single scan is inexpensive
Jump Search (O(1)) (O(sqrt{n})) (O(sqrt{n})) (O(1)) Sorted data accessed in sequential blocks
Binary Search (O(1)) (O(log n)) (O(log n)) (O(1)) Random access to a sorted array is available

Jump Search is not asymptotically optimal in comparison count: binary search is faster for ordinary random-access arrays. Jump Search can still be useful when sequential block transfers are cheaper than many isolated probes.

Common Search Variants

  • First or last occurrence: For duplicates, keep scanning the identified block and save the first or last matching index.

  • Lower and upper bounds: Python’s bisect_left and bisect_right implement binary-search-based insertion boundaries for sorted lists.

  • Rotated sorted array: First locate the rotation point with binary search, then search the appropriate sorted half.

  • Binary search on an answer: When a feasibility condition is monotonic, binary search over the possible answer range is generally preferable to Jump Search.

Code Example

from math import isqrt


def jump_search(values: list[int], target: int) -> int:
    """Return the first index of target in a sorted list, or -1 if absent."""
    size = len(values)

    if size == 0:
        return -1

    if values[0] == target:
        return 0

    block_size = isqrt(size)
    block_start = 0

    while block_start < size:
        block_end = min(block_start + block_size - 1, size - 1)

        if values[block_end] >= target:
            # The target, if present, must be within this block.
            for index in range(block_start, block_end + 1):
                if values[index] == target:
                    return index
            return -1

        block_start = block_end + 1

    return -1


values = [-5, 1, 3, 3, 7, 9, 12]
print(jump_search(values, 7))  # Expected output: 4

Common Pitfalls

  • Unsorted input: Jump Search’s skip decision is invalid unless the array is sorted.

  • Incorrect boundaries: The implementation uses inclusive block boundaries and correctly handles a final partial block.

  • Duplicate values: This version returns the first occurrence; finding the last occurrence requires continuing the block scan.

  • Edge cases: Empty lists return -1, a one-element list works normally, and negative values require no special handling.

  • Input mutation: The implementation does not reorder or modify the list.

  • Interview follow-ups: Common questions cover binary-search lower and upper bounds, first and last occurrence, rotated arrays, and searching a monotonic answer space.

23

What is Exponential Search in sorted arrays?

Exponential Search, also called Galloping Search, first finds a range containing the target by repeatedly doubling its position, then performs binary search within that range. It is especially efficient when the target is likely near the beginning of a sorted collection.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm has two phases:

  1. Exponential expansion

  2. Check positions 1, 2, 4, 8, and so on until the target should be within the current range.

  3. This grows the candidate interval exponentially rather than searching the entire array immediately.

  4. Binary search

  5. Apply binary search to the identified interval.

  6. Use an inclusive interval, [lower, right].

  7. Calculate mid = lower + (right - lower) // 2, avoiding overflow from lower + right in fixed-width languages.

For example, searching for 16 in [2, 4, 8, 16, 32] proceeds as follows:

  1. Position 1 contains 4, which is less than 16; double to position 2.

  2. Position 2 contains 8, which is less than 16; double to position 4.

  3. Position 4 contains 32, so the target is within positions 2 through 4.

  4. Binary search finds 16 at index 3.

Unlike ordinary binary search, exponential search can avoid examining the latter half of a large collection when the target is close to the beginning.

Related Search Approaches

Approach Time Extra space When to use
Linear search O(n) O(1) Unsorted data, very small collections, or when only one pass is possible
Binary search O(log n) O(1) Sorted data, or another monotonic condition, when the target may be anywhere
Exponential search O(log(k + 1)) O(1) Sorted data where the target may be near the beginning

Here, k is approximately the target’s position. Exponential search’s worst case is still O(log n), but it can significantly reduce the initial search range for an early target.

Other common search variants include:

  • First or last occurrence: Use bisect_left to find the first value greater than or equal to the target and bisect_right to find the first value greater than it.

  • Rotated sorted array: Identify the rotation boundary, then use binary search in the relevant sorted portion; time is O(log n).

  • Binary search on an answer: Search a numeric range for the smallest value satisfying a monotonic predicate, such as minimum shipping capacity; time is O(log R), where R is the search range.

  • Graph search: Use BFS or DFS to find reachable nodes, with O(V + E) time for an adjacency-list representation.

Complexity

  • Best-case time: O(1) — the target is found at the first position.

  • Average-case time: O(log n) — expansion and binary search each require logarithmically many steps.

  • Worst-case time: O(log n) — doubling reaches the end of the collection, and the remaining binary-search interval has logarithmic size.

  • Auxiliary space: O(1) — only a fixed number of variables are used; there is no recursion stack, and the input collection is not counted.

Common Pitfalls and Interview Tips

  • Requires sorted input: Randomly doubling indices does not make an unsorted collection searchable.

  • Handle the boundary correctly: The doubling phase may exceed the collection length, and the target may be exactly at the doubled position.

  • Avoid integer overflow: In Java or C++, doubling can overflow; use a wider type or stop before overflow.

  • Duplicate values: A plain exponential search returns a matching index, not necessarily the first or last occurrence. Use bisect_left and bisect_right when those specific positions matter.

  • Edge cases: Return a not-found value such as -1 for empty input; one-element input and negative numbers need no special handling.

  • Follow-up questions: Interviewers commonly ask why exponential search beats binary search for early targets, how it handles absent values, and how it would be adapted to a sorted stream of unknown length.

24

Exponential Search vs Interpolation Search: time complexity and use cases

Exponential Search and Interpolation Search are both algorithms for finding a target value in a sorted array, but they differ in how they narrow the search range and in their performance assumptions. Exponential Search first finds a bounding range by repeatedly doubling an index, then runs binary search inside that range; it excels when the target is near the start or the array is unbounded. Interpolation Search estimates the target’s position using a linear interpolation formula, achieving O(log log n) average time on uniformly distributed data but degrading to O(n) on skewed distributions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Exponential Search Works

  1. If the first element matches the target, return immediately.

  2. Set bound = 1. While bound < n and arr[bound] < target, double bound.

  3. Perform binary search on indices bound // 2 through min(bound, n - 1), inclusive (in Python slice terms, arr[bound // 2 : min(bound + 1, n)]).

Example walkthrough (array [1, 3, 5, 7, 9, 11, 13, 15], target 9): 1. arr[0] = 1 != 9. 2. bound = 1: arr[1] = 3 < 9 → bound = 2. 3. bound = 2: arr[2] = 5 < 9 → bound = 4. 4. bound = 4: arr[4] = 9 not < 9, stop doubling. 5. Binary search between indices 2 and 4 finds 9 at index 4.

How Interpolation Search Works

  1. Maintain low and high pointers.

  2. Compute probe position:
    pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])

  3. If arr[pos] == target, return pos; otherwise adjust low or high and repeat.

Example walkthrough (array [10, 20, 30, 40, 50], target 30): 1. low = 0, high = 4. 2. pos = 0 + ((30-10)*(4-0))//(50-10) = 2. 3. arr[2] = 30 → return 2.

Time and Space Complexity

Algorithm Best Case Average Case Worst Case Space (iterative) Space (recursive)
Exponential Search O(1) (target at index 0) O(log i) where i is target index (O(log n) if uniform) O(log n) O(1) O(log n)
Interpolation Search O(1) (exact guess) O(log log n) (uniform distribution) O(n) (skewed data) O(1) O(log n)

Input array not counted in space complexity.

When to Use Each

Scenario Preferred Algorithm Reason
Unbounded / infinite sorted stream Exponential Search No prior knowledge of upper bound; finds range dynamically
Target likely near beginning Exponential Search Range discovery takes O(log i) steps, very fast for small i
Large array, uniform numeric keys Interpolation Search O(log log n) average beats binary search’s O(log n)
Non-uniform or unknown distribution Exponential Search (or binary search) Interpolation degrades to O(n); exponential guarantees O(log n)
Integer keys with duplicates Exponential Search Interpolation formula can stall when arr[high] == arr[low]

Key Differences

  • Distribution sensitivity: Interpolation Search assumes uniform distribution; Exponential Search makes no distribution assumption.

  • Data type: Interpolation requires numeric keys supporting subtraction and division; Exponential works with any comparable type.

  • Implementation complexity: Exponential Search is simpler (loop + binary search); Interpolation needs careful handling of division by zero and integer overflow in other languages.

  • Practical performance: On modern hardware with cache effects, binary search often outperforms interpolation search unless n is very large (>10⁶) and distribution is truly uniform.

Common Pitfalls

  • Interpolation division by zero: Always check arr[high] != arr[low] before computing pos; fall back to binary search or linear scan when equal.

  • Integer overflow in pos formula: In languages with fixed-width integers, compute as low + (target - arr[low]) * (high - low) // (arr[high] - arr[low]) using wider type or rearrange to avoid overflow.

  • Assuming interpolation is always faster: For small arrays or non-uniform data, binary/exponential search is faster due to lower constant factors.

  • Forgetting exponential search’s first-element check: Without it, the doubling loop starts at index 1 and misses index 0.

  • Using interpolation on non-numeric keys: The formula requires arithmetic operations; it cannot be used on strings or custom objects without a numeric mapping.

  • Interview follow-up: “How would you modify exponential search to find the first occurrence of a duplicate target?” → After finding any match, run binary search on the left subarray for the lower bound. “Can interpolation search work on a rotated sorted array?” → No, the monotonicity assumption breaks; use modified binary search instead.

25

How does ternary search find a value in sorted data?

Ternary search is a divide-and-conquer algorithm that searches sorted or otherwise monotonic data by dividing the remaining interval into three parts instead of two. It compares the target with two pivots to determine which third can contain the answer.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For an ascending sorted array, ternary search maintains an inclusive interval [left, right] and calculates two pivot positions:

  • mid1 is approximately one-third into the interval.

  • mid2 is approximately two-thirds into the interval.

The target is compared with both pivots:

  1. If target == values[mid1] or target == values[mid2], the search succeeds.

  2. If target < values[mid1], continue in the left third.

  3. If target > values[mid2], continue in the right third.

  4. Otherwise, continue in the middle section between the pivots.

Each iteration discards roughly two-thirds of the remaining elements, giving the recurrence T(n) = T(n/3) + O(1).

For example, searching for 7 in [1, 3, 5, 7, 9, 11, 13]:

  1. The pivots are 5 and 9; 7 lies between them.

  2. The remaining interval becomes [7].

  3. The next pivot is 7, so the algorithm returns its index.

Complexity and Alternatives

Algorithm Best time Average time Worst time Extra space Sorted data required?
Linear search O(1) O(n) O(n) O(1) No
Binary search O(1) O(log n) O(log n) O(1) Yes
Ternary search O(1) O(log n) O(log n) O(1) Yes
  • Time: Ternary search takes O(log₃ n), which is asymptotically O(log n), because each iteration reduces the interval to about one-third.

  • Space: The iterative implementation uses O(1) auxiliary space. The input array is not counted. A recursive implementation would use O(log n) recursion-stack space.

  • Practical choice: Ternary search does not improve the asymptotic complexity over binary search. Binary search is usually preferred because it is simpler and uses one midpoint per iteration.

Related Search Variants

  • First and last occurrence: With duplicates, continue searching left or right after finding an equal value to locate the first or last occurrence respectively. In Python, bisect_left finds the first position where a value could be inserted while preserving order, and bisect_right finds the position after all equal values.

  • Lower and upper bounds: bisect_left(values, target) returns the first index whose value is at least target; bisect_right(values, target) returns the first index whose value is greater than target.

  • Rotated sorted array: Use modified binary search to determine which half is sorted. Keep an inclusive interval [lo, hi] and calculate mid = lo + (hi - lo) // 2; this avoids overflow in fixed-width languages compared with (lo + hi) // 2.

  • Binary search on an answer: Search over a numeric range when a monotonic predicate is true or false, such as finding the minimum capacity needed for a task. This is different from searching for an exact array element.

Code Example

def ternary_search(values: list[int], target: int) -> int:
    """Return an index of target in a sorted ascending list, or -1."""
    left = 0
    right = len(values) - 1

    while left <= right:
        third = (right - left) // 3
        mid1 = left + third
        mid2 = right - third

        if values[mid1] == target:
            return mid1
        if values[mid2] == target:
            return mid2

        if target < values[mid1]:
            right = mid1 - 1
        elif target > values[mid2]:
            left = mid2 + 1
        else:
            left = mid1 + 1
            right = mid2 - 1

    return -1


if __name__ == "__main__":
    data = [1, 3, 5, 7, 9, 11, 13]
    print(ternary_search(data, 7))  # 3

Common Pitfalls

  • Unsorted input: Ternary search requires ascending or descending order. Without sorting or a monotonic condition, interval elimination can discard the target.

  • Duplicate values: The implementation returns any matching pivot, not necessarily the first or last occurrence.

  • Empty and single-element inputs: Empty input returns -1; a single-element input is handled without an out-of-range access.

  • Off-by-one errors: This implementation uses the inclusive interval [left, right], so updates use mid1 - 1 and mid2 + 1.

  • Mutating input: Sorting the data before searching changes its order; avoid modifying the caller’s list unless that is intended.

  • Recursion depth: The iterative version avoids Python’s recursion-depth limit.

27

How do you implement ternary search for a unimodal array’s local maximum?

Ternary search finds a local maximum in a unimodal array by comparing values at two points that divide the remaining interval into thirds, then discarding a third that cannot contain the peak. In a strictly unimodal array, the local maximum is also the global maximum.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The search maintains an inclusive interval [left, right]. Two comparison positions are calculated:

  • m1 = left + (right - left) // 3

  • m2 = right - (right - left) // 3

The values at these positions divide the interval into three approximately equal parts:

  • If values[m1] < values[m2], the array is still rising at m1, so the maximum must be to the right of m1. Set left = m1 + 1.

  • If values[m1] > values[m2], the array is descending at m2, so the maximum must be to the left of m2. Set right = m2 - 1.

  • When the values are equal, the array contains duplicates. Because a flat section can make the peak ambiguous, the implementation safely returns the index of the maximum value.

The formulas use left and right rather than adding a large offset directly, avoiding integer-overflow problems in languages with fixed-width integers.

Complexity

Input case Best time Average time Worst time Auxiliary space
Strictly unimodal, no duplicates O(log n) O(log n) O(log n) O(1)
Duplicate-aware fallback O(log n) O(n) when a duplicate is encountered O(n) O(1)

Each ternary-search iteration removes roughly one third of the remaining interval, giving O(log₃ n), which is conventionally written as O(log n). The input sequence is not counted in the space complexity.

Walkthrough

For [1, 3, 7, 9, 5, 2]:

  1. left = 0, right = 5; m1 = 1 and m2 = 4.

  2. values[m1] = 3 and values[m2] = 5, so discard the left third and set left = 2.

  3. The interval is now [7, 9, 5, 2]; m1 = 3 and m2 = 4.

  4. values[m1] = 9 and values[m2] = 5, so discard the right portion and set right = 3.

  5. The interval contains [7, 9]; the right-hand value is larger, so set left = 3.

  6. The algorithm returns index 3, whose value is 9.

Code Example

from collections.abc import Sequence


def find_local_maximum(values: Sequence[int]) -> int | None:
    """Return an index of a local maximum in a unimodal sequence."""
    if not values:
        return None

    left, right = 0, len(values) - 1

    while left < right:
        m1 = left + (right - left) // 3
        m2 = right - (right - left) // 3

        if values[m1] == values[m2]:
            # Duplicates can form a flat section. For a weakly unimodal
            # array, a maximum-valued position is a non-strict local maximum.
            return max(range(len(values)), key=values.__getitem__)

        if values[m1] < values[m2]:
            # The peak is to the right of m1.
            left = m1 + 1
        else:
            # The peak is to the left of m2.
            right = m2 - 1

    return left


print(find_local_maximum([1, 3, 7, 9, 5, 2]))  # 3

Common Pitfalls

  • Unimodal precondition: The array must increase and then decrease; an arbitrary array does not guarantee that ternary search preserves the peak.

  • Local-maximum definition: With duplicate values, use the non-strict definition values[i] >= values[i - 1] and values[i] >= values[i + 1]; a plateau may contain several equally valid maximum positions.

  • Empty and single-element inputs: Empty input returns None; a one-element input returns index 0.

  • Sorted input: An increasing array has its peak at the final element, while a decreasing array has its peak at the first element.

  • Negative values: Comparisons work normally; no special handling is needed.

  • Off-by-one errors: This implementation uses the inclusive interval [left, right] and updates it with m1 + 1 and m2 - 1.

  • Input mutation: The function does not modify the input sequence.

  • Disconnected graphs and cycles: These do not apply to this linear-array search; they are relevant only when searching graphs with BFS or DFS.

28

What is the efficiency of divide-and-conquer searching on unimodal and bitonic sequences?

Divide-and-conquer search achieves O(log n) time on unimodal and bitonic sequences because each comparison identifies a half that cannot contain the required turning point or result. Searching a known bitonic shape remains O(log n) overall because locating the turning point and then searching its monotonic arms are both logarithmic.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

  • Unimodal sequence: Values increase toward one peak and then decrease. A target may occur on either side of the peak, so locating the peak first makes both sides searchable as monotonic sections.

  • Bitonic sequence: Values are monotonic in one direction and then the other. The increasing-then-decreasing form is a “mountain”; the decreasing-then-increasing form is a “valley.” Their searches use mirrored comparisons.

  • Divide-and-conquer principle: Compare a midpoint with the target or an adjacent value, discard the half that cannot contain the answer, and continue in the remaining half.

  • Required assumption: The sequence must have the stated unimodal or bitonic structure. Ordinary binary search cannot safely search an arbitrary unsorted sequence.

Efficiency Comparison

Approach Best time Average time Worst time Auxiliary space When to use
Linear search O(1) O(n) O(n) O(1) Any sequence, including unsorted data
Binary search on a monotonic section O(1) O(log n) O(log n) O(1) iterative The section is consistently ascending or descending
Locate the peak of a unimodal sequence O(log n) O(log n) O(log n) O(1) iterative The sequence has one peak
Locate the turning point of a bitonic sequence O(log n) O(log n) O(log n) O(1) iterative The sequence has one peak or valley
Locate the turning point, then search its arms O(log n) O(log n) O(log n) O(1) iterative A target may occur on either monotonic arm
Brute-force target search O(1) O(n) O(n) O(1) No usable monotonic structure is available

Linear search examines up to n elements. Each divide-and-conquer comparison discards approximately half of the current interval, giving O(log n) time. Searching both arms after locating the turning point performs a constant number of logarithmic searches, so the total remains O(log n).

Auxiliary space is O(1) for iterative implementations and O(log n) for recursive implementations because of the recursion stack. These figures exclude the input sequence itself.

How the Search Works

  1. Start with the closed interval [lo, hi], initially with hi = n - 1.

  2. Calculate mid = lo + (hi - lo) // 2. In fixed-width languages, this avoids overflow that can occur when calculating (lo + hi) // 2; Python integers do not overflow.

  3. For a mountain peak, compare values[mid] with values[mid + 1]:

  4. If values[mid] < values[mid + 1], the peak lies to the right.

  5. If values[mid] > values[mid + 1], the peak lies at mid or to its left.

  6. If they are equal, the direction may be ambiguous, particularly around a duplicated peak.

  7. For a valley, reverse these comparisons.

  8. After locating the turning point, check it separately and search the two monotonic arms with binary search. Search both arms when the same target may occur on both sides.

Using a half-open interval [lo, hi) avoids invalid mid + 1 access when mid is the final valid index.

Example Walkthrough

Consider the bitonic mountain [1, 3, 5, 4, 2].

  1. lo = 0, hi = 4, and mid = 2.

  2. Since values[2] = 5 is greater than values[3] = 4, the peak is at index 2 or earlier. Set hi = 2.

  3. Now lo = 0, hi = 2, and mid = 1.

  4. Since values[1] = 3 is less than values[2] = 5, the peak lies to the right. Set lo = 2.

  5. The peak is index 2 with value 5. The left arm is [1, 3], the right arm is [4, 2], and the target 4 lies on the descending right arm.

Related Search Variants

  • Lower and upper bounds: On an ascending sorted list, bisect_left returns the lower-bound position and bisect_right returns the upper-bound position.

  • First and last occurrence: The first occurrence is bisect_left(values, target) when that position contains the target; the last is bisect_right(values, target) - 1.

  • Rotated sorted array: Finding the rotation point and then searching takes O(log n) time for distinct values and O(1) auxiliary space iteratively. Duplicates can cause the worst case to degrade to O(n).

  • Binary search on an answer: A monotonic condition over a numeric range of size R can be minimized or maximized in O(log R) time and O(1) auxiliary space iteratively.

  • Interpolation search: It can achieve O(log log n) average time on uniformly distributed data but may degrade to O(n); its auxiliary space is O(1).

Common Pitfalls

  • Applying ordinary binary search to the whole sequence without first accounting for its peak or valley.

  • Updating a closed interval incorrectly and accidentally excluding the turning point.

  • Assuming adjacent midpoint values are always different; duplicates can make the turning-point direction ambiguous.

  • Counting the input as auxiliary space or ignoring the recursive call stack.

  • Treating a two-peak or cyclic sequence as a standard bitonic sequence.

  • Forgetting edge cases: empty input has no result, a singleton is the sole peak and valley, negative values do not affect the comparisons, and already monotonic input can use ordinary binary search directly.

29

Why use binary search on a doubly linked list?

Binary search is usually not a performance optimization for a plain doubly linked list because it lacks random access. Its value is primarily conceptual: sorted order permits logarithmic comparisons, but the pointer traversal needed to find each midpoint makes the overall search linear.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Rationale

Binary search relies on two properties:

  • Sorted or monotonic data: each comparison identifies a portion that can be discarded.

  • Constant-time midpoint access: arrays provide this through indexing.

A doubly linked list provides constant-time access to a node’s next and previous pointers, but it does not provide constant-time access to its middle node. Consequently, each binary-search iteration may require linear pointer traversal.

For example, searching for 7 in 1 → 3 → 5 → 7 → 9:

  1. Find the midpoint, 5.

  2. Compare 7 with 5, then discard the portion through 5.

  3. Find the midpoint of the remaining range, 7.

  4. Return the successful result.

There are only logarithmically many value comparisons, but the cumulative pointer traversal is linear.

The familiar array implementation can use the half-open interval [lo, hi) and mid = lo + (hi - lo) // 2. Subtracting before adding prevents overflow in fixed-width languages; Python integers do not overflow. This calculation does not solve the linked list’s midpoint-access problem.

Time and Space Complexity

Approach Best time Average time Worst time Auxiliary space
Binary search on a sorted array O(1) O(log n) O(log n) O(1)
Midpoint-based binary search on a doubly linked list O(n) O(n) O(n) O(1)
Linear search on a doubly linked list O(1) O(n) O(n) O(1)

For the linked-list simulation, repeated range traversal and midpoint finding cost approximately n + n/2 + n/4 + ... = O(n). Auxiliary space is O(1) because only pointers and counters are needed; the input list’s nodes are not counted as auxiliary space.

When the Approach Makes Sense

  • Educational demonstration: It illustrates binary-search reasoning independently of array indexing.

  • Augmented structures: A skip list provides expected O(log n) lookup, while a balanced search tree provides O(log n) lookup.

  • Static, frequently searched data: Copying the list into an array once costs O(n); each subsequent array search can then take O(log n).

  • Few searches: Linear search is usually simpler because both approaches take O(n) overall for a plain doubly linked list.

bisect_left and bisect_right operate efficiently on a sorted Python list because indexed access is O(1). They cannot be applied efficiently to an ordinary linked list without additional indexing or augmentation.

Related Binary-Search Variants

  • First or last occurrence: On a sorted array, continue searching left or right after an equality match. A linked-list version still incurs pointer-traversal costs and must define how duplicates are handled.

  • Lower and upper bounds: bisect_left and bisect_right find insertion boundaries in a sorted Python list in O(log n) time.

  • Rotated sorted array: A modified binary search can locate a target in O(log n) time under assumptions such as distinct values; duplicates may require a linear fallback. A plain linked list still loses the benefit of constant-time indexed access.

  • Binary search on the answer: This technique searches a numeric domain using a monotonic feasibility predicate. It is independent of whether the underlying data is stored in an array or linked list.

Common Pitfalls

  • Claiming O(log n) runtime for a plain linked list: Only the comparison count is logarithmic; midpoint traversal keeps total time O(n).

  • Confusing pointer access with indexing: Accessing next or previous is O(1), but locating an indexed midpoint is not.

  • Ignoring ordering requirements: The values must already be sorted in the direction used by the comparisons.

  • Handling duplicates incorrectly: Finding any occurrence differs from finding the first or last occurrence.

  • Edge cases: An empty list has no match, a one-element list can be checked directly, and negative values work when the list is sorted consistently.

  • Malformed structures: Cycles or broken next/previous links can cause failed or non-terminating traversal; production implementations should preserve or validate list invariants.

30

How do hash tables perform search operations under collisions?

Collision resolution lets a hash table search a bucket containing multiple keys by comparing the stored keys until it finds a match or exhausts the bucket. Separate chaining and open addressing are the two common strategies, giving O(1) expected lookup but O(n) worst-case lookup.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Collision Handling Works

  1. Compute hash(key).

  2. Convert the hash into a bucket index, commonly with hash(key) % capacity.

  3. Resolve collisions:

  4. Separate chaining: Scan the linked list, list, or other collection stored in the bucket.

  5. Open addressing: Probe other slots using linear probing, quadratic probing, double hashing, or another rule.

  6. Compare stored keys with the requested key using equality, not hash-value equality.

  7. Return the associated value or report that the key is absent.

With open addressing, an empty slot normally terminates the search. Deletions generally require tombstones; physically emptying a slot can break later probe sequences.

Complexity and Trade-offs

Strategy Best time Average time Worst time Lookup auxiliary space
Separate chaining O(1) O(1) expected O(n) O(1)
Linear probing O(1) O(1) expected O(n) O(1)
Quadratic probing O(1) O(1) expected O(n) O(1)
Double hashing O(1) O(1) expected O(n) O(1)

The average bounds assume a good hash function and controlled load factor. Poor hashing or excessive load can concentrate keys in one bucket and make a lookup approach O(n).

Total table storage is O(n) for n stored entries. A lookup uses O(1) auxiliary space, excluding the table itself; it does not copy the input and has no recursion stack. Insertion and update are O(1) expected, O(n) worst case for a long chain, and amortized O(1) when resizing is included.

Linear and Binary Search Context

A linear search across the whole table takes O(1) best case and O(n) average and worst cases, with O(1) auxiliary space. Binary search over sorted data takes O(1) best case and O(log n) average and worst cases, also with O(1) auxiliary space. A sorted collision bucket of size k can be searched in O(1) best case and O(log k) average and worst cases.

Related binary-search variants include:

  • First/last occurrence: On a sorted list, derive the first equal index from bisect_left and the last from bisect_right - 1. Each boundary query takes O(log n) time and O(1) auxiliary space.

  • Lower/upper bound: bisect_left finds the first index whose value is not less than the target; bisect_right finds the first index whose value is greater than the target.

  • Rotated sorted array: Detect the sorted half and restrict the search accordingly. With distinct values, the standard algorithm takes O(1) best case and O(log n) average and worst cases with O(1) space; duplicates can degrade the search to O(n).

  • Binary search on an answer: Search a numeric range using a monotonic feasibility predicate. With O(1) feasibility checks, it takes O(log R) time in the best, average, and worst cases for R candidates, because locating the threshold needs every halving step, with O(1) auxiliary space.

Edge Cases

  • An empty table or empty collision bucket returns None.

  • A one-element table is handled normally.

  • Assigning an existing key updates its value without creating another entry.

  • Negative values are supported because only keys are hashed.

  • The sorted-bucket helper handles an empty bucket, but unsorted entries violate its precondition.

Code Example

class HashTable:
    """A separate-chaining hash table with amortized resizing."""

    def __init__(self) -> None:
        self._buckets: list[list[tuple[str, int]]] = [[] for _ in range(8)]
        self._size: int = 0

    def _index(self, key: str) -> int:
        return hash(key) % len(self._buckets)

    def put(self, key: str, value: int) -> None:
        bucket = self._buckets[self._index(key)]

        for position, entry in enumerate(bucket):
            if entry[0] == key:
                bucket[position] = (key, value)
                return

        bucket.append((key, value))
        self._size += 1

        if self._size > len(self._buckets) * 0.75:
            self._rehash()

    def _rehash(self) -> None:
        old_buckets = self._buckets
        self._buckets = [[] for _ in range(len(old_buckets) * 2)]

        for bucket in old_buckets:
            for key, value in bucket:
                self._buckets[self._index(key)].append((key, value))

    def search(self, key: str) -> int | None:
        """Return the value associated with key, or None if it is absent."""
        for stored_key, value in self._buckets[self._index(key)]:
            if stored_key == key:
                return value
        return None


def binary_search_sorted_bucket(
    bucket: list[tuple[str, int]], key: str
) -> int | None:
    """Search a bucket whose entries are sorted by key."""
    lo, hi = 0, len(bucket) - 1  # Inclusive interval [lo, hi].

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        mid_key, mid_value = bucket[mid]

        if mid_key == key:
            return mid_value
        if mid_key < key:
            lo = mid + 1
        else:
            hi = mid - 1

    return None


table = HashTable()
table.put("name", 2)
table.put("name", 7)
print(table.search("name"))  # 7

The midpoint expression lo + (hi - lo) // 2 avoids integer overflow possible with (lo + hi) // 2 in fixed-width languages.

Common Pitfalls

  • Do not compare hash values instead of keys: different keys can have identical hashes.

  • Maintain a reasonable load factor: resize before collisions become excessive.

  • Handle tombstones correctly when deleting from open-addressed tables.

  • Do not assume a hash table is sorted: binary search requires sorted keys.

  • Avoid list.pop(0) and list.insert(0, value) in chains: both are O(n) operations.

  • Define duplicate-key behavior deliberately: this implementation updates the existing value.

  • Keep hashed keys immutable: changing a key’s contents can invalidate its stored hash and make it unreachable.

31

How does Breadth-First Search traverse a graph level by level?

Breadth-First Search (BFS) traverses a graph level by level, visiting all vertices at the current distance before moving to the next level. It uses a first-in, first-out queue and finds a path with the fewest edges from the starting vertex in an unweighted graph.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How BFS Works

  1. Add the starting vertex to the queue and mark it as visited.

  2. Remove the vertex at the front of the queue.

  3. Add that vertex to the traversal result.

  4. Examine its neighbors:

  5. Add each unvisited neighbor to the queue.

  6. Mark the neighbor immediately when it is enqueued.

  7. Repeat until the queue is empty.

The FIFO behavior is essential: vertices discovered earlier are processed earlier, so vertices at distance 1 are processed before vertices at distance 2.

BFS does not require sorted data. In contrast, linear search takes (O(n)), while binary search takes (O(log n)) but requires sorted data or another monotonic condition; neither replaces graph traversal in an arbitrary graph.

Example Walkthrough

For these adjacency lists:

  • A: B, C

  • B: D

  • C: D, E

  • D: F

  • E: F

The traversal proceeds as follows:

Step Removed Queue after processing
1 A B, C
2 B C, D
3 C D, E
4 D E, F
5 E F
6 F Empty

The result is A, B, C, D, E, F. If a vertex has multiple parents, the result can vary depending on adjacency-list order.

Complexity

Let (V) be the number of vertices and (E) the number of edges in the reachable portion of the graph.

  • Time: (O(V + E)). Each reachable vertex is dequeued once, and each adjacency-list entry is examined once; an undirected edge can be represented from both endpoints.

  • Auxiliary space: (O(V)). The queue and visited set can each hold up to (O(V)) vertices. This iterative implementation uses no recursion stack and excludes the input graph and returned traversal order.

  • Including output: (O(V)), because the result stores up to (V) vertices.

  • Best case: (O(1)) for an empty graph, an invalid starting vertex, or an isolated valid starting vertex.

  • Average and worst case: (O(V + E)) for a normal traversal.

For a disconnected graph, BFS visits only the connected component containing the starting vertex unless the algorithm is explicitly run from additional starting vertices.

Code Example

from collections import deque


def breadth_first_search(
    graph: dict[str, list[str]],
    start: str,
) -> list[str]:
    """Return vertices reachable from start in breadth-first order."""
    if start not in graph:
        return []

    visited = {start}
    queue = deque([start])
    traversal_order: list[str] = []

    while queue:
        current = queue.popleft()
        traversal_order.append(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                # Mark when enqueued to prevent duplicate queue entries.
                visited.add(neighbor)
                queue.append(neighbor)

    return traversal_order


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["F"],
    "E": ["F"],
}

print(breadth_first_search(graph, "A"))
# Expected output: ['A', 'B', 'C', 'D', 'E', 'F']

Common Pitfalls

  • Marking vertices only when dequeued: This can place the same vertex in the queue multiple times. Mark each vertex when it is enqueued.

  • Using a list with pop(0): Removing the first list element is (O(n)). Use collections.deque, whose front removal is (O(1)).

  • Ignoring cycles: A visited set prevents a cycle from causing infinite traversal.

  • Forgetting disconnected components: Standard BFS visits only vertices reachable from its starting vertex.

  • Assuming shortest weighted paths: BFS guarantees the fewest-edge path in an unweighted graph. Use Dijkstra’s algorithm for graphs with non-negative weighted edges.

  • Changing input unnecessarily: The example does not mutate the adjacency lists, making traversal order predictable and preserving caller-owned data.

32

How does Depth-First Search traverse a graph?

Depth-First Search (DFS) is a graph traversal algorithm that follows one path as deeply as possible before backtracking to explore unvisited branches. It uses a visited set to prevent revisiting vertices and can be implemented recursively or with an explicit stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The basic DFS process is:

  1. Start at a source vertex.

  2. Mark the current vertex as visited.

  3. Explore one unvisited neighbor.

  4. Continue deeper from that neighbor.

  5. If no unvisited neighbors remain, backtrack to the previous vertex.

  6. Repeat until all reachable vertices have been visited.

For example, consider this adjacency list:

  • 1: 2, 3

  • 2: 4

  • 3: 4, 5

  • 4: none

  • 5: none

A DFS beginning at 1 proceeds as follows:

  1. Visit 1, then enter 2.

  2. Visit 2, then enter 4.

  3. Visit 4; because it has no unvisited neighbors, backtrack to 2.

  4. Vertex 2 is exhausted, so backtrack to 1.

  5. Visit 3; skip the already visited 4, then visit 5.

The discovery order is 1 → 2 → 4 → 3 → 5. The exact order depends on the order in which neighbors are examined and on the implementation.

DFS is useful for:

  • Finding connected components

  • Detecting cycles

  • Topological sorting

  • Searching for a path

  • Solving maze and backtracking problems

Traversal Variants

  • Recursive DFS: Calls itself for each unvisited neighbor. It is concise, but recursion depth can exceed Python’s default limit of approximately 1000 nested calls.

  • Iterative DFS: Uses an explicit stack of frames. It avoids recursion-limit issues and is safer for large or deeply nested graphs.

  • DFS with early termination: Stops as soon as a target is found, without necessarily computing the full traversal order.

  • DFS across disconnected graphs: When no start vertex is specified, a separate DFS must begin in each unvisited component.

Complexity

For an adjacency-list graph with V vertices and E edges:

  • Time: Best, average, and worst case are all O(V + E) for a complete traversal because each vertex is visited once and each adjacency-list entry is examined once.

  • Auxiliary space: O(V) for the visited set and explicit stack, excluding the input graph. A recursive implementation also uses O(V) recursion-stack space in the worst case.

For an adjacency matrix:

  • Time: Best, average, and worst case are all O(V²) because rows may need to be scanned.

  • Auxiliary space: O(V) for the visited set and stack, excluding the input matrix.

Algorithm Best time Average time Worst time Auxiliary space Requirement
DFS on adjacency lists O(V + E) O(V + E) O(V + E) O(V) Graph traversal
Linear search O(1) O(n) O(n) O(1) Unsorted data
Binary search O(1) O(log n) O(log n) O(1) iterative, O(log n) recursive Sorted data or a monotonic condition

Code Example

The following iterative implementation uses one stack frame per active vertex, preserves neighbor order, and supports disconnected graphs when start is None.

Edge cases: an empty graph returns []; a one-vertex graph returns that vertex; repeated neighbor entries do not cause duplicate visits; negative integer labels work; cycles terminate because vertices are marked when discovered; and disconnected components are visited when start is None. Sorted versus unsorted adjacency lists has no algorithmic significance, although the implementation preserves the listed order.

from collections.abc import Mapping, Sequence


def depth_first_search(
    graph: Mapping[int, Sequence[int]],
    start: int | None = None,
) -> list[int]:
    """Return vertices in depth-first discovery order."""
    if start is not None and start not in graph:
        raise ValueError(f"Start vertex {start} is not in the graph")

    visited: set[int] = set()
    order: list[int] = []
    roots = iter(graph.keys()) if start is None else iter((start,))

    for root in roots:
        if root in visited:
            continue

        visited.add(root)
        order.append(root)

        # Each frame stores a vertex and its next neighbor index.
        stack: list[tuple[int, int]] = [(root, 0)]

        while stack:
            vertex, neighbor_index = stack[-1]
            neighbors = graph.get(vertex, ())

            if neighbor_index == len(neighbors):
                stack.pop()
                continue

            neighbor = neighbors[neighbor_index]
            stack[-1] = (vertex, neighbor_index + 1)

            if neighbor not in visited:
                visited.add(neighbor)
                order.append(neighbor)
                stack.append((neighbor, 0))

    return order


graph = {
    1: [2, 3],
    2: [4],
    3: [4, 5],
    4: [],
    5: [],
    6: [7],
    7: [],
}

print(depth_first_search(graph))  # Expected output: [1, 2, 4, 3, 5, 6, 7]

Best Practices

  • Mark vertices when discovered, before adding their frames, to prevent duplicate processing and handle cycles.

  • Use an explicit stack for large graphs or graphs with long paths.

  • Validate that a specified start vertex exists in the graph.

  • For disconnected graphs, begin a new traversal from every unvisited vertex.

  • Use adjacency lists for O(V + E) traversal; this bound can still equal O(V²) for a dense graph.

  • Preserve neighbor order when a deterministic traversal order is required.

Common Pitfalls

  • Missing the visited set: A cycle can cause infinite recursion or repeated processing.

  • Recursion depth: A long path can exceed Python’s recursion limit; use an explicit stack or carefully raise the limit.

  • Ignoring disconnected components: Searching from only one vertex can miss unrelated parts of the graph.

  • Mutating the graph during traversal: Changes to adjacency lists can make the traversal order unpredictable.

  • Applying binary search to arbitrary data: Binary search requires sorted data or a monotonic condition; ordinary graph traversal uses DFS or BFS.

34

How do you detect a cycle in an undirected graph with BFS?

A cycle exists in an undirected graph when BFS encounters an already visited vertex through an edge other than the edge used to discover that vertex. Tracking both visited vertices and parent edges also handles disconnected graphs and distinguishes parallel edges correctly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Run BFS from every unvisited vertex so that disconnected components are checked.

For each vertex, store the unique ID of the edge through which it was discovered:

  • Skip the parent edge: It leads back to the vertex from which the current vertex was discovered.

  • Visit an unvisited neighbor: Mark it visited and record the current edge as its parent edge.

  • Encounter a visited neighbor through another edge: The edge closes a cycle, so return True.

Unique edge IDs are useful because two parallel edges between the same vertices form a 2-edge cycle. For a simple graph without parallel edges, tracking the parent vertex is sufficient.

Complexity

Let V be the number of vertices and E the number of edges.

Case Time Reason
Best O(1) The graph is empty, or the first inspected edge exposes a cycle immediately
Average O(V + E) Each vertex is processed once and each adjacency entry is inspected once
Worst O(V + E) The entire graph may be explored before finding a cycle or confirming none exists
  • Auxiliary space: O(V), excluding the input graph, for visited, parent_edge, and the BFS queue.

  • Total space including input: O(V + E).

  • Recursion stack: O(1), because the implementation is iterative.

  • O(V + E) time is asymptotically optimal for an explicitly stored adjacency list.

Walkthrough

Consider the triangle 0–1–2–0 with edge IDs e0, e1, and e2.

  1. Start BFS at 0 and mark it visited.

  2. From 0, visit 1 through e0.

  3. From 1, skip e0 and visit 2 through e1.

  4. From 2, skip parent edge e1.

  5. From 2, encounter 0 through e2. Since 0 is visited and e2 is not the parent edge, a cycle is detected.

Code Example

from collections import deque


def has_cycle(graph: dict[int, list[tuple[int, int]]]) -> bool:
    """Return whether an undirected graph contains a cycle."""
    visited: set[int] = set()
    parent_edge: dict[int, int | None] = {}

    for start in graph:
        if start in visited:
            continue

        visited.add(start)
        parent_edge[start] = None
        queue: deque[int] = deque([start])

        while queue:
            vertex = queue.popleft()

            for neighbor, edge_id in graph.get(vertex, []):
                # Ignore only the exact edge used to discover this vertex.
                if edge_id == parent_edge[vertex]:
                    continue

                if neighbor not in visited:
                    visited.add(neighbor)
                    parent_edge[neighbor] = edge_id
                    queue.append(neighbor)
                else:
                    # A non-parent edge reaches an already visited vertex.
                    return True

    return False


def add_undirected_edge(
    graph: dict[int, list[tuple[int, int]]],
    left: int,
    right: int,
    edge_id: int,
) -> None:
    """Add an undirected edge with a globally unique ID."""
    graph.setdefault(left, []).append((right, edge_id))
    if left != right:
        graph.setdefault(right, []).append((left, edge_id))


if __name__ == "__main__":
    graph: dict[int, list[tuple[int, int]]] = {}
    add_undirected_edge(graph, 0, 1, 0)
    add_undirected_edge(graph, 1, 2, 1)
    add_undirected_edge(graph, 2, 0, 2)
    graph[3] = []  # Disconnected isolated vertex

    print(has_cycle(graph))  # True

Edge Cases

  • Empty graph: Returns False.

  • One isolated vertex: Returns False.

  • Self-loop: Returns True; a self-loop is a cycle of length one.

  • Parallel edges: Returns True when they have different edge IDs, representing a 2-edge cycle.

  • Disconnected graph: BFS starts a new traversal for each unvisited component.

  • Acyclic disconnected graph: Returns False after checking every component.

  • Negative or duplicate vertex labels: Labels have no effect; each dictionary key represents one vertex.

Common Pitfalls

  • Forgetting visited: BFS can revisit vertices repeatedly and may report the wrong edge.

  • Skipping every edge to the parent vertex: This misses cycles formed by parallel edges; skip only the parent edge ID.

  • Checking only one component: A cycle may exist outside the component containing the first vertex.

  • Marking vertices visited too late: Mark a vertex when it is enqueued to avoid adding it to the queue multiple times.

  • Assuming cycles require at least three vertices: That convention applies to simple graphs; multigraphs may contain self-loops and 2-edge cycles.

  • Interview follow-up: Compare BFS with DFS, discuss cycle detection in directed graphs using recursion-stack states, and explain why a topological sort also detects cycles.

35

Which search algorithm is fastest for a given data set?

No search algorithm is universally fastest; the best choice depends on ordering, query count, and whether the data can be preprocessed. For sorted data, binary search is the standard choice and reduces lookup to O(log n); for unsorted data, linear search takes O(n) in the worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Choosing the Algorithm

  • Unsorted data or only a few queries: Use linear search. Sorting first costs O(n log n) and may not be worthwhile.

  • Sorted data: Use binary search, which requires the values to be sorted in the search order.

  • Repeated queries: Sorting once may be worthwhile when the number of queries is large enough to amortize the O(n log n) sorting cost.

  • Python sorted lists: Use bisect_left and bisect_right for lower- and upper-bound searches.

  • Search over a numeric answer range: Use binary search on the answer when the feasibility condition is monotonic.

  • Small data sets: Linear search may be faster in practice because binary search has additional bookkeeping.

Complexity Comparison

Approach Best time Average time Worst time Auxiliary space
Linear search O(1) O(n) O(n) O(1)
Binary search O(1) O(log n) O(log n) O(1)
bisect_left / bisect_right O(log n) O(log n) O(log n) O(1)

Linear search examines elements until it finds a match, so it takes O(1) when the first element matches and up to O(n) otherwise. Binary search repeatedly halves the remaining interval, requiring O(log n) comparisons except when an early probe succeeds. bisect_left and bisect_right also halve the search interval and therefore take O(log n) time.

The auxiliary-space figures exclude the input itself. These searches can be implemented iteratively using only a few variables, so they use O(1) space and have no recursion stack.

How Binary Search Works

Binary search maintains a closed, inclusive interval [lo, hi].

  1. Compute mid = lo + (hi - lo) // 2.

  2. Compare the target with values[mid].

  3. Discard the half that cannot contain the target.

  4. Continue until the target is found or lo > hi.

The midpoint formula avoids overflow in fixed-width languages: (lo + hi) // 2 can exceed the maximum integer value, while lo + (hi - lo) // 2 cannot.

Search Variants

Variant Method or behavior Time complexity Auxiliary space
First occurrence bisect_left(values, target) O(log n) O(1)
Last occurrence bisect_right(values, target) - 1, when present O(log n) O(1)
Lower bound First index whose value is at least the target O(log n) O(1)
Upper bound First index whose value is greater than the target O(log n) O(1)
Rotated sorted array Identify the sorted half and discard the other half Distinct values: best O(1), average/worst O(log n); duplicates can cause O(n) worst case O(1)
Binary search on the answer Binary-search a monotonic feasibility predicate Best O(C), average/worst O(C log R) O(1) search state, excluding the check’s internal memory

For binary search on the answer, C is the cost of one feasibility check and R is the number of candidate answers. The logarithmic factor comes from repeatedly halving the candidate range.

Example Walkthrough

For values = [2, 4, 4, 7, 9] and target = 4:

  1. Binary search starts with lo = 0 and hi = 4.

  2. It computes mid = 2, where values[2] == 4, so it returns index 2.

  3. bisect_left returns 1, identifying the first 4.

  4. bisect_right returns 4; subtracting one gives index 3, the last 4.

Common Pitfalls

  • Unsorted input: Binary search produces incorrect results unless the values are sorted.

  • Off-by-one errors: Clearly choose between inclusive [lo, hi] and exclusive [lo, hi) intervals.

  • Duplicate values: Ordinary binary search may return any matching index; use lower and upper bounds for the first or last occurrence.

  • Unexpected mutation: Do not sort the input unless permitted; sorting costs O(n log n) and may invalidate the performance advantage.

  • Edge cases: Empty input, one element, negative numbers, and already sorted input require no special algorithmic change.

  • Interview follow-up: Interviewers commonly ask about first or last occurrence, missing targets, lower and upper bounds, rotated arrays, or searching a numeric answer range.

36

How does balancing a search tree preserve efficient search operations?

Balancing a search tree keeps its height (h) at (O(log n)), so lookup, insertion, and deletion remain efficient instead of degrading to (O(n)) in a skewed tree. Self-balancing structures enforce this invariant through rotations, rebalancing, or node splitting.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Balancing Works

A binary search tree stores smaller keys in the left subtree and larger keys in the right. Its search cost depends on the number of nodes visited along one root-to-leaf path, which is proportional to its height.

  • Unbalanced tree: Height can reach (O(n)), so an unlucky search may visit every node.

  • Balanced tree: Height is restricted to (O(log n)), making search, insertion, and deletion (O(log n)) in the worst case.

  • AVL invariant: The heights of the left and right subtrees differ by at most one.

  • Rebalancing: After insertion or deletion, rotations such as left and right rotations restore the invariant while preserving key order.

For example, inserting 10, 20, and 30 produces a right-skewed tree. An AVL tree performs a left rotation, leaving 20 as the root with children 10 and 30.

Balancing Strategies

  • AVL trees: Use the strict height invariant. They provide fast lookups but may require more rotations during updates.

  • Red-black trees: Use color constraints and a black-height invariant. They generally perform fewer rotations and are common in ordered-map implementations.

  • B-trees: Store multiple keys per node and are better suited to disks, SSDs, and databases.

  • Randomized trees (treaps): Give each key a random priority and use rotations to keep those priorities in heap order, giving expected (O(log n)) height.

Complexity

Approach Best Average Worst Auxiliary space
Linear search (O(1)) (O(n)) (O(n)) (O(1))
Binary search on sorted data (O(1)) (O(log n)) (O(log n)) (O(1))
Unbalanced BST lookup (O(1)) (O(log n)) for a typical random tree (O(n)) (O(1))
Balanced-tree lookup (O(1)) (O(log n)) (O(log n)) (O(1))
Balanced-tree insertion (O(1)) (O(log n)) (O(log n)) (O(log n)) path storage

These auxiliary-space bounds exclude the input and the tree itself. The stored tree requires (O(n)) space. The implementation below is iterative, so it has no recursion stack; its ancestor path uses (O(log n)) space.

Binary Search Variants

  • Lower and upper bounds: On a sorted list, bisect_left finds the first index where a key can be inserted without violating order, while bisect_right finds the first index after all equal keys.

  • First or last occurrence: First occurrence is bisect_left; last occurrence is bisect_right - 1, when the key exists.

  • Rotated sorted array: With distinct values, identify the sorted half, then binary-search that half in (O(log n)).

  • Binary search on an answer: Search the smallest value satisfying a monotonic predicate, such as minimum shipping capacity or an integer square root.

  • The code uses the interval [lo, hi) and mid = lo + (hi - lo) // 2. Although Python integers do not overflow, this form also avoids overflow in fixed-width languages.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class _Node:
    key: int
    height: int = 1
    left: _Node | None = None
    right: _Node | None = None


class AVLTree:
    """AVL tree supporting duplicate-rejecting insertion and lookup."""

    def __init__(self) -> None:
        self.root: _Node | None = None

    @staticmethod
    def _height(node: _Node | None) -> int:
        return 0 if node is None else node.height

    @staticmethod
    def _update_height(node: _Node) -> None:
        node.height = 1 + max(
            AVLTree._height(node.left),
            AVLTree._height(node.right),
        )

    @staticmethod
    def _rotate_left(node: _Node) -> _Node:
        promoted = node.right
        assert promoted is not None
        node.right = promoted.left
        promoted.left = node
        AVLTree._update_height(node)
        AVLTree._update_height(promoted)
        return promoted

    @staticmethod
    def _rotate_right(node: _Node) -> _Node:
        promoted = node.left
        assert promoted is not None
        node.left = promoted.right
        promoted.right = node
        AVLTree._update_height(node)
        AVLTree._update_height(promoted)
        return promoted

    @classmethod
    def _rebalance(cls, node: _Node) -> _Node:
        cls._update_height(node)
        balance = cls._height(node.left) - cls._height(node.right)

        if balance > 1:
            left = node.left
            assert left is not None
            if cls._height(left.left) < cls._height(left.right):
                node.left = cls._rotate_left(left)
            return cls._rotate_right(node)

        if balance < -1:
            right = node.right
            assert right is not None
            if cls._height(right.right) < cls._height(right.left):
                node.right = cls._rotate_right(right)
            return cls._rotate_left(node)

        return node

    def insert(self, key: int) -> bool:
        """Insert a key; return False when the key already exists."""
        if self.root is None:
            self.root = _Node(key)
            return True

        path: list[_Node] = []
        current = self.root

        while current is not None:
            path.append(current)
            if key == current.key:
                return False
            current = current.left if key < current.key else current.right

        parent = path[-1]
        new_node = _Node(key)
        if key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        # Restore the AVL invariant while walking toward the root.
        for index in range(len(path) - 1, -1, -1):
            node = path[index]
            if index == 0:
                self.root = self._rebalance(node)
            else:
                ancestor = path[index - 1]
                rebuilt = self._rebalance(node)
                if ancestor.left is node:
                    ancestor.left = rebuilt
                else:
                    ancestor.right = rebuilt

        return True

    def search(self, key: int) -> bool:
        """Return whether key exists in the tree."""
        current = self.root
        while current is not None:
            if key == current.key:
                return True
            current = current.left if key < current.key else current.right
        return False

    def height(self) -> int:
        """Return height in edges, using -1 for an empty tree."""
        return -1 if self.root is None else self.root.height - 1


def binary_search(values: list[int], target: int) -> bool:
    """Search a sorted list using the half-open interval [lo, hi)."""
    lo, hi = 0, len(values)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] == target:
            return True
        if target < values[mid]:
            hi = mid
        else:
            lo = mid + 1

    return False


tree = AVLTree()
for value in (10, 20, 30, 40, 50):
    tree.insert(value)

result = (
    tree.search(30),
    tree.search(99),
    tree.height(),
    binary_search([10, 20, 30, 40, 50], 30),
)
print(result)
# Expected: (True, False, 2, True)

Common Pitfalls

  • Confusing inclusive [lo, hi] with half-open [lo, hi) bounds causes off-by-one errors.

  • Failing to update subtree heights after rotations breaks the AVL invariant.

  • Forgetting to rebalance after deletion is a common update-path error.

  • Empty trees, single nodes, duplicates, negative keys, and already sorted inputs are handled above; duplicates are ignored.

  • Binary search requires sorted data; it does not sort or mutate the input.

  • Common follow-up questions compare AVL and red-black trees, explain rotations, or analyze deletion and height maintenance.

37

How can heuristics optimize search queries in non-sortable datasets?

Heuristic-guided search predicts where a matching record is most likely to be located, probes those candidates first, and falls back to an exhaustive scan when necessary. It can substantially reduce average query latency when predictions are accurate, but it cannot guarantee logarithmic search because a non-sortable dataset provides no ordering invariant for safely discarding candidates.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Heuristic Search Works

A practical heuristic-guided search follows these steps:

  1. Predict a candidate region: Use metadata, historical statistics, or a learned model to estimate which partition or records are most relevant.

  2. Probe likely candidates first: Search the predicted partition or highest-ranked candidates.

  3. Verify every candidate: A match is accepted only after comparing the actual query criteria.

  4. Fall back when necessary: If the prediction was wrong, scan the remaining data to preserve exact search semantics.

For example, records might be partitioned by region, category, or date bucket. If a query is more likely to match west, the system examines that bucket before searching east and other buckets.

The heuristic changes only the search order. It must not discard candidates permanently unless approximate search semantics are acceptable.

Complexity and Search Alternatives

All implementations below are iterative and use O(1) auxiliary space, excluding the input data itself.

Approach Best time Average or expected time Worst time When to use
Linear search O(1) O(n) O(n) Unsorted data with no useful heuristic
Binary search O(1) O(log n) O(log n) Sorted data or a monotonic predicate
Partition heuristic O(1) O(1 + p·m + (1-p)·n) O(n) Accurately predictable partitions
Auxiliary hash index O(1) O(1) O(n) Exact key-based lookups

For the partition heuristic, p is the probability that the predicted partition is correct and m is the maximum number of records in that partition. If p is close to 1 and m is much smaller than n, expected work approaches O(m). Without a useful prediction, the method remains O(n).

Binary Search Boundaries and Variants

Binary search requires sorted data or a monotonic condition; arbitrary non-sortable data cannot safely eliminate half the search space.

  • Lower bound: Find the first index whose value is greater than or equal to the target. Python provides bisect_left.

  • Upper bound: Find the first index whose value is greater than the target. Python provides bisect_right.

  • First occurrence: Compute the lower bound and check whether that element equals the target.

  • Last occurrence: Compute the upper bound and subtract one.

  • Rotated sorted array: Identify the rotation pivot, then binary-search the half that can contain the target. Duplicate values complicate pivot detection.

  • Binary search on the answer: Binary-search a numeric range using a monotonic predicate, such as “can all items be carried by capacity c?” This can find minimum capacity or an integer square root without a sorted array.

Choosing a Useful Heuristic

Good prediction signals include:

  • Partition metadata: Region, product category, tenant, or date bucket.

  • Historical statistics: Frequently accessed records or successful query paths.

  • Similarity estimates: Query-to-record similarity scores that rank promising candidates.

  • Freshness or popularity: Recently created or commonly returned records.

  • Learned ranking: A model that estimates the probability that a record satisfies a query.

For frequent exact lookups, a hash table or inverted index is usually better than a heuristic because it provides stronger guarantees.

Step-by-Step Walkthrough

The following trace shows how heuristic_search finds record 12 in the example data:

  1. Input: partitions = {"west": [Record(10), Record(12)], "east": [Record(11)]}, target_id = 12, predicted_partition = "west".

  2. Predicted partition lookup: partitions.get("west") returns the sequence [Record(10), Record(12)].

  3. Scan predicted partition:

  4. Compare Record(10).record_id (10) with target (12) → no match.

  5. Compare Record(12).record_id (12) with target (12) → match found.

  6. Return Record(12, "gamma") immediately; the east partition is never examined.

  7. If the target were 99 (not present): the predicted partition scan would finish without a match, then the fallback loop would scan east (and any other partitions) before returning None.

Code Example

from bisect import bisect_left, bisect_right
from collections.abc import Mapping, Sequence
from dataclasses import dataclass


@dataclass(frozen=True)
class Record:
    record_id: int
    payload: str


def lower_bound(values: Sequence[int], target: int) -> int:
    """Return the first index whose value is greater than or equal to target."""
    lo, hi = 0, len(values)  # Search interval is [lo, hi).

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid

    return lo


def heuristic_search(
    partitions: Mapping[str, Sequence[Record]],
    target_id: int,
    predicted_partition: str,
) -> Record | None:
    """Search a predicted partition first, then fall back to all partitions."""
    predicted_records = partitions.get(predicted_partition)

    if predicted_records is not None:
        for record in predicted_records:
            if record.record_id == target_id:
                return record

    for partition_name, records in partitions.items():
        if partition_name == predicted_partition:
            continue

        for record in records:
            if record.record_id == target_id:
                return record

    return None


records_by_partition = {
    "west": (Record(10, "alpha"), Record(12, "gamma")),
    "east": (Record(11, "beta"),),
}

values = [1, 2, 2, 4]

print(lower_bound(values, 2))          # 1
print(bisect_left(values, 2))          # 1
print(bisect_right(values, 2))         # 3
print(heuristic_search(records_by_partition, 12, "west"))
# Record(record_id=12, payload='gamma')
print(heuristic_search(records_by_partition, 99, "west"))
# None

For the example, the heuristic predicts west. The search checks west directly, finds record 12 while scanning that bucket, and returns it without examining east. If the prediction is incorrect or the record does not exist, the fallback scans the remaining partitions.

The mid = lo + (hi - lo) // 2 formula avoids overflow from lo + hi in fixed-width languages such as Java and C++. Python integers do not overflow, but the formula remains portable.

Common Pitfalls

  • Dropping the fallback: A heuristic prediction can be wrong. Removing fallback behavior makes the result incomplete.

  • Assuming binary search works on arbitrary data: Without sorted or monotonic behavior, binary search may discard the actual match.

  • Using ambiguous keys: If multiple records can share an id, define which one is returned or use a compound key.

  • Mutating the input: Partition maps and record collections should remain unchanged during a query.

  • Ignoring edge cases: Empty input returns None; one-element input works normally; negative identifiers are valid; sorted order is irrelevant. Disconnected graphs and cycles are graph-specific and do not apply here.

  • Underestimating fallback cost: The worst case remains O(n), regardless of how accurate the heuristic appears during testing.

Interviewers commonly ask for the heuristic’s hit rate, expected and worst-case complexity, fallback behavior, and how the approach differs from building an exact hash or inverted index.

38

How do you search an infinite or unknown-length data stream?

Use a one-pass streaming search: consume values until a match is found or a monotonic stopping condition proves that no match can occur later. An arbitrary infinite stream cannot prove that a value is absent because new values may arrive indefinitely.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Strategy

  • Unsorted stream: perform a linear scan for each value. Return immediately on a match. If the finite stream is exhausted, return “not found”; on an infinite stream, absence cannot be established.

  • Ascending sorted stream: stop at the first value greater than or equal to the target. If it equals the target, a match exists; if it is greater, sortedness proves the target cannot occur later.

  • Infinite sorted stream: assuming the values eventually exceed the target, the same lower-bound scan terminates without knowing the stream length.

  • Random-access source: if indexed access is available, use exponential search to find a containing range, followed by binary search.

For an ordinary iterator, reaching position k requires inspecting k elements, so a linear scan is asymptotically optimal for a one-pass sequential stream.

Related Variants

  • Lower bound: the first position whose value is at least the target. In Python, bisect_left finds this in a sorted random-access list.

  • Upper bound: the first position whose value is greater than the target. bisect_right finds this.

  • First or last occurrence: use the lower and upper bounds; the last occurrence is immediately before the upper bound.

  • Rotated sorted array: use a modified binary search that first identifies the sorted half.

  • Binary search on the answer: search a monotonic predicate over a finite domain; it is not directly applicable to an unbounded domain.

  • Infinite random-access sequence: exponential search can locate an upper bound in O(log k) accesses. Binary search then operates on the inclusive interval [lo, hi], using mid = lo + (hi - lo) // 2 to avoid overflow in fixed-width languages.

Complexity

For a finite stream containing n elements:

Approach Best Average Worst Auxiliary space
Sequential streaming search O(1) O(n) O(n) O(1)
Binary search on sorted random-access data O(log n) O(log n) O(log n) O(1)
Exponential search plus binary search O(log k) O(log k) O(log k) O(1)
  • The streaming average assumes the target is equally likely to occupy any position.

  • On an infinite stream with no match, the search runs indefinitely, so there is no finite worst-case bound.

  • Auxiliary space is O(1), including the absence of recursion. The input stream itself is not counted.

  • For a sorted stream, if the lower bound has rank k, the search takes O(k) time.

Code Example

from collections.abc import Iterable


def search_sorted_stream(
    stream: Iterable[int], target: int
) -> tuple[bool, int | None]:
    """Return the lower bound and whether it equals the target."""
    for value in stream:
        if value >= target:
            return value == target, value
    return False, None


values = iter([-5, 2, 2, 4, 7])
print(search_sorted_stream(values, 3))  # (False, 4)

The function handles empty and one-element streams, duplicates, and negative values. It assumes ascending order. For an unsorted stream, replace the value >= target stopping condition with equality and continue until a match or exhaustion.

Walkthrough

For the sorted stream [-5, 2, 2, 4, 7] and target 3:

  1. Inspect -5: it is below 3, so continue.

  2. Inspect 2: it is below 3, so continue.

  3. Inspect the next 2: it is still below 3.

  4. Inspect 4: it is the first value at least 3.

  5. Return (False, 4): the lower bound is 4, and the target is absent.

Common Pitfalls

  • Do not call len() or index a stream: generators and network streams may have unknown or inaccessible lengths.

  • Do not use binary search on an ordinary iterator: binary search requires random access.

  • Do not stop at value > target for unsorted data: a later value could still equal the target.

  • Do not claim “not found” on an arbitrary infinite stream: absence is unprovable without exhaustion or a monotonic stopping condition.

  • Do not materialize the stream: list(stream) may consume unbounded memory.

  • Do not confuse the first and last occurrence: a first match is obtainable in one pass, but the last match generally requires seeing the rest of the data.

  • Avoid list.pop(0) or list.insert(0, x): both are O(n) operations and are unnecessary here.

39

How do you implement backtracking search for context-dependent conditions?

Backtracking explores possible choices recursively while maintaining the context needed to evaluate the target condition. When a branch cannot produce a valid result, the algorithm undoes that choice and explores an alternative.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A backtracking algorithm typically maintains a partial solution and context:

  1. Choose a candidate.

  2. Update the context, such as a running sum or remaining capacity.

  3. Recursively explore choices consistent with that context.

  4. If the branch fails, undo the choice and try another.

  5. Stop when the condition is satisfied or no choices remain.

For example, finding a subset with a target sum uses remaining and path as context:

Step Remaining Path
Start 7 []
Choose 2 5 [2]
Choose 3 2 [2, 3]
4 exceeds remaining 2 [2, 3]
Undo failed choices 7 []
Choose 3, then 4 0 [3, 4]

Complexity

For the subset-sum backtracking example with n candidates:

  • Best time: O(n) for this implementation — the input check scans every candidate first; the search itself can succeed after a single choice (for example, when the first element equals the target).

  • Average time: O(2^n) conservative bound — pruning often reduces the search, but no tighter bound applies without assumptions about the input distribution.

  • Worst time: O(2^n) — the search may explore a binary include-or-exclude decision tree.

  • Extra space: O(n) — the recursion stack and current path each grow to O(n). The input sequence itself is not copied or counted.

Code Example

from collections.abc import Sequence


def find_subset_sum(
    candidates: Sequence[int], target: int
) -> list[int] | None:
    """Return one subset of non-negative candidates that sums to target."""
    if target < 0:
        raise ValueError("target must be non-negative")
    if any(value < 0 for value in candidates):
        raise ValueError("candidates must be non-negative")

    path: list[int] = []

    def backtrack(start: int, remaining: int) -> bool:
        if remaining == 0:
            return True

        for index in range(start, len(candidates)):
            value = candidates[index]
            if value > remaining:
                continue

            path.append(value)
            if backtrack(index + 1, remaining - value):
                return True
            path.pop()  # Undo this choice before exploring another branch.

        return False

    if not backtrack(0, target):
        return None

    return path.copy()


print(find_subset_sum([2, 3, 4], 7))  # [3, 4]
print(find_subset_sum([], 0))         # []
print(find_subset_sum([1, 2], 5))     # None

Common Pitfalls

  • Failing to undo state: Every failed branch must restore the path, counters, or other mutable context.

  • Invalid pruning: value > remaining is safe here only because negative candidates are rejected.

  • Duplicate values: Each occurrence is treated as a separate candidate; duplicate values may legitimately appear in the result.

  • Empty input: A target of zero returns []; a positive target returns None.

  • Recursion depth: The recursive implementation can exceed Python’s default depth of roughly 1,000 calls. Use an explicit stack or carefully raise the recursion limit for very large inputs.

  • Input mutation: The implementation reads but does not modify candidates.

40

How does Monte Carlo Tree Search work in game AI?

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm that builds a game-state tree by repeatedly selecting, expanding, simulating, and backing up rewards. It is especially useful when a fast simulator or learned model is available.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How MCTS Works

Each iteration has four stages:

  1. Selection: Descend from the root through expanded children, choosing the action with the highest Upper Confidence Bound for Trees: UCT(state, action) = Q(state, action) + c × sqrt(log(N(state)) / N(state, action)). Here, Q is the action’s average reward, N is its visit count, and c controls exploration.

  2. Expansion: Add one child for an untried action at the selected node.

  3. Simulation: Run a rollout using a fast policy until termination or a configured limit.

  4. Backup: Propagate the terminal reward or heuristic evaluation through the selected path.

The final action is usually the root child with the most visits. In adversarial games, rewards must be converted to the appropriate player’s perspective, often through sign changes between turns.

Game AI Applications

Application How MCTS is used
Chess, Go, and shogi Combines self-play with learned policy and value estimates.
Atari-style games MuZero searches with learned latent dynamics, reward, and value predictions.
Strategy and tactics Evaluates build orders, unit movements, and possible responses.
Robotics and planning Uses a simulator to explore actions before real-world execution.

Complexity

Let T be the iteration count, d the maximum selection depth, B the maximum children scanned at a node, A the maximum legal-action count, h the maximum rollout length, and S the state-copy or evaluation cost.

  • Best: O(T(A + S)) when selection depth and rollout length are minimal.

  • Average: O(T(dB + A + S)) plus the average rollout cost.

  • Worst: O(T(dB + A + h + S)).

At most one node is added per iteration, so at most T + 1 nodes are stored. Auxiliary space is O(T(A + S)), or O(T) when action count and state size are constants. The input is not counted, and the iterative implementation uses no recursion stack.

Small Walkthrough

With the player at 0, the coin at 2, and two moves remaining:

Iteration Expansion Simulated result Reward
1 Move left to -1 Move right to 0 0
2 Move right to 1 Move right to 2 1
Later Root is fully expanded The successful branch receives more visits Move right

Code Example

from __future__ import annotations

from collections import deque
from collections.abc import Callable, Hashable
from dataclasses import dataclass
from math import log, sqrt
from random import Random
from typing import Generic, TypeVar

StateT = TypeVar("StateT")
ActionT = TypeVar("ActionT", bound=Hashable)


@dataclass
class _Node(Generic[StateT, ActionT]):
    state: StateT
    untried_actions: deque[ActionT]
    children: dict[ActionT, _Node[StateT, ActionT]]
    visits: int = 0
    total_reward: float = 0.0


def monte_carlo_tree_search(
    initial_state: StateT,
    legal_actions: Callable[[StateT], list[ActionT]],
    apply_action: Callable[[StateT, ActionT], StateT],
    is_terminal: Callable[[StateT], bool],
    rollout: Callable[[StateT, Random], float],
    iterations: int = 1000,
    exploration: float = sqrt(2.0),
    seed: int = 0,
) -> ActionT | None:
    """Return the most-visited action, or None for invalid iterations/no actions."""
    if iterations <= 0:
        return None

    rng = Random(seed)

    def new_node(state: StateT) -> _Node[StateT, ActionT]:
        # Preserve order while removing duplicate actions.
        unique_actions = dict.fromkeys(legal_actions(state))
        return _Node(state, deque(unique_actions), {})

    root = new_node(initial_state)

    def uct(parent: _Node[StateT, ActionT], action: ActionT) -> float:
        child = parent.children[action]
        if child.visits == 0:
            return float("inf")

        exploitation = child.total_reward / child.visits
        exploration_term = exploration * sqrt(
            log(max(parent.visits, 1)) / child.visits
        )
        return exploitation + exploration_term

    for _iteration in range(iterations):
        node = root
        path: list[_Node[StateT, ActionT]] = []

        # Selection: descend only through already-expanded children.
        while (
            not is_terminal(node.state)
            and not node.untried_actions
            and node.children
        ):
            action = max(node.children, key=lambda candidate: uct(node, candidate))
            child = node.children[action]
            path.append(child)
            node = child

        # Expansion: add at most one child.
        if not is_terminal(node.state) and node.untried_actions:
            action = node.untried_actions.popleft()
            child = new_node(apply_action(node.state, action))
            node.children[action] = child
            path.append(child)
            node = child

        # Simulation.
        reward = rollout(node.state, rng)

        # Backup: increment every node in the path exactly once.
        for visited_node in reversed(path):
            visited_node.visits += 1
            visited_node.total_reward += reward
        root.visits += 1
        root.total_reward += reward

    if not root.children:
        return None

    return max(root.children, key=lambda action: root.children[action].visits)


@dataclass(frozen=True)
class CoinState:
    position: int
    coin: int
    steps_left: int


def legal_actions(state: CoinState) -> list[int]:
    if state.steps_left <= 0:
        return []
    return [-1, 1]


def apply_action(state: CoinState, action: int) -> CoinState:
    return CoinState(
        position=state.position + action,
        coin=state.coin,
        steps_left=state.steps_left - 1,
    )


def is_terminal(state: CoinState) -> bool:
    return state.steps_left <= 0


def rollout(state: CoinState, rng: Random) -> float:
    current = state
    while not is_terminal(current):
        direction = 1 if current.position < current.coin else -1
        current = apply_action(current, direction)
    return 1.0 if current.position == current.coin else 0.0


initial_state = CoinState(position=0, coin=2, steps_left=2)
best_action = monte_carlo_tree_search(
    initial_state,
    legal_actions,
    apply_action,
    is_terminal,
    rollout,
    iterations=100,
)
print(best_action)  # Expected output: 1

Common Pitfalls

  • Wrong reward perspective: Failing to change reward signs between adversarial turns makes the search optimize for the wrong player.

  • Poor rollouts: A biased rollout policy produces misleading estimates even when selection is correct.

  • Excessive exploration: A large exploration constant wastes iterations, while a small one causes premature commitment.

  • Incorrect terminal handling: Terminal states must not be expanded or assigned legal actions.

  • Uncontrolled simulation cost: Long rollouts can make each iteration too slow for real-time play.

  • Edge cases: An empty action set or terminal initial state returns None; one action is handled normally, duplicates are removed, and negative positions are valid.

Common follow-ups include tuning exploration, handling imperfect information, comparing MCTS with minimax, and explaining why visit counts are more robust than raw rollout rewards.

41

What is approximate string matching and where is it used?

Approximate string matching finds occurrences of a pattern even when they differ slightly from it, or more generally identifies and ranks strings according to their similarity. It commonly uses an edit-distance threshold that permits a limited number of insertions, deletions, or substitutions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

In its broader form, approximate string matching searches a text for a pattern that occurs approximately rather than exactly. Comparing two complete strings with an edit distance is one common formulation used by search and data-cleaning systems.

  • Levenshtein distance: Minimum number of single-character insertions, deletions, or substitutions required to transform one string into the other.

  • Damerau–Levenshtein distance: Extends Levenshtein distance by allowing adjacent characters to be transposed.

  • Similarity threshold: The maximum permitted distance at which two strings are still considered similar.

For example, "Jon Smyth" and "John Smith" have a Levenshtein distance of 2: insert h into "Jon" and substitute i for y in "Smyth".

The standard dynamic-programming recurrence is:

D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + cost)

The alternatives represent deletion, insertion, and substitution or exact match, respectively. The cost is 0 for equal characters and 1 otherwise.

Where It Is Used

  • Typo-tolerant search: Finds relevant results despite misspelled queries or keyboard errors.

  • Spelling correction: Suggests corrections by comparing an incorrect word with known words.

  • Autocomplete: Matches incomplete or slightly misspelled prefixes against indexed terms.

  • Duplicate detection: Groups records whose names or descriptions differ by small formatting or spelling changes.

  • Data cleaning and record linkage: Identifies records referring to the same entity despite minor inconsistencies.

Searching Strategies

Let t be the number of candidates, n a candidate string’s length, m the pattern length, and L the maximum exact-key length.

Approach Best time Average time Worst time Extra space When to use
Linear scan of t exact candidates O(1) O(t) O(t) O(1) Small or unsorted collections
Binary search over t sorted exact keys O(1) key comparison, or O(L) character work O(log t) key comparisons, or O(L log t) character work O(log t) key comparisons, or O(L log t) character work O(1) Exact matching in sorted keys
Levenshtein distance for one pair O(nm) O(nm) O(nm) O(min(n, m)) Similarity against one pattern
Full Levenshtein calculation for every candidate O(tnm) O(tnm) O(tnm) O(min(n, m)) Small collections requiring fuzzy matching

Binary search requires sorted data or a monotonic condition. A standard binary search cannot directly find the nearest fuzzy match because edit distance is not necessarily monotonic in lexicographic order.

Related binary-search variants include:

  • First occurrence: Use bisect_left on sorted values and verify that the located value equals the target.

  • Last occurrence: Use bisect_right minus one and verify equality.

  • Lower and upper bounds: bisect_left and bisect_right locate insertion positions in sorted exact values.

  • Rotated sorted arrays: Modified binary search identifies the sorted region before continuing.

  • Binary search on an answer: Use when feasibility is monotonic, such as searching for a minimum capacity.

The space figures are auxiliary space and exclude the input. An iterative dynamic-programming implementation uses two rows and adds no recursion-stack space.

Example Walkthrough

Comparing pattern "cat" with text "cut" produces these dynamic-programming states:

Text prefix ↓ / Pattern prefix → Empty c ca cat
Empty 0 1 2 3
c 1 0 1 2
cu 2 1 1 2
cut 3 2 2 1

The final distance is 1, so the strings match when the permitted threshold is at least 1.

Common Pitfalls

  • Empty input: An empty pattern matches an empty string and can match a nonempty string when its length is within the threshold. A nonempty pattern matches an empty string only when the threshold is at least the pattern length.

  • Duplicates: Edit distance handles repeated characters correctly; identical strings always have distance 0.

  • Negative thresholds: No match should be possible when the permitted distance is negative.

  • Already sorted input: Sorting is unnecessary for linear scanning but enables binary search for exact keys.

  • Case sensitivity: Normalize case only when product requirements call for it; otherwise "Cat" and "cat" differ by one substitution.

  • Metric choice: Levenshtein distance does not count a transposition as one edit; use Damerau–Levenshtein when transpositions matter.

  • Unicode: Python indexes Unicode code points, so normalization may be needed when combining characters or other multi-code-point forms matter.

  • Performance: For large corpora, consider an inverted index, n-gram index, or dedicated fuzzy-search library instead of calculating edit distance for every candidate.

42

How do you find the k closest points to an origin?

Use a bounded max-heap to retain the k smallest distances while scanning all points once. Squared Euclidean distance preserves distance ordering and avoids calculating square roots.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each point, calculate its squared Euclidean distance from the origin:

distance_squared = Σ (point[i] - origin[i])²

Maintain a max-heap containing at most k points:

  1. If the heap contains fewer than k points, insert the new point.

  2. Otherwise, compare the new point with the heap root, which represents the farthest retained point.

  3. Replace the root only when the new point is closer.

  4. Sort the final heap by distance before returning it.

Python’s heapq is a min-heap, so negative distances are stored to simulate a max-heap.

Complexity

Let n be the number of points and d the number of dimensions.

Approach Time Extra space When to use
Compute distances and sort all points O(nd + n log n) O(n) When a fully sorted result is required
Bounded max-heap O(nd + n log(k + 1)) O(k) When only the k closest points are needed

For the heap approach, best, average, and worst-case time are all O(nd + n log(k + 1)): every point is scanned and at most one heap operation is performed per point. The final O(k log k) sort is covered by the overall bound because k ≤ n. Auxiliary space is O(k), excluding the input. The input is not copied or mutated, and there is no recursion, so the recursion-stack space is O(1).

Step-by-Step Example

For origin = (0, 0) and k = 3:

Point Squared distance Heap action Retained distances
(1, 0) 1 Insert 1
(3, 0) 9 Insert 1, 9
(0, 2) 4 Insert 1, 4, 9
(-1, 0) 1 Replace distance 9 1, 1, 4
(0, -1) 1 Replace distance 4 1, 1, 1

The result contains the three points at distance 1.

Code Example

from collections.abc import Sequence
from heapq import heappush, heapreplace

Point = tuple[float, ...]


def k_closest_points(
    points: Sequence[Point],
    origin: Point,
    k: int,
) -> list[Point]:
    """Return k points nearest to origin by Euclidean distance."""
    if k < 0:
        raise ValueError("k must be non-negative")
    if k == 0:
        return []
    if not points or k > len(points):
        raise ValueError("k must not exceed the number of points")

    dimension = len(origin)
    if any(len(point) != dimension for point in points):
        raise ValueError("Every point must have the same dimension as origin")

    # Entries are (-squared_distance, point), forming a max-heap by distance.
    max_heap: list[tuple[float, Point]] = []

    for point in points:
        squared_distance = sum(
            (coordinate - origin_coordinate) ** 2
            for coordinate, origin_coordinate in zip(point, origin)
        )
        entry = (-squared_distance, point)

        if len(max_heap) < k:
            heappush(max_heap, entry)
        elif entry[0] > max_heap[0][0]:
            # The candidate is closer than the farthest retained point.
            heapreplace(max_heap, entry)

    # Negating the stored distance restores ascending distance order.
    return [
        point
        for _, point in sorted(
            max_heap,
            key=lambda item: (-item[0], item[1]),
        )
    ]


points = [(1, 0), (3, 0), (0, 2), (-1, 0), (0, -1)]
print(k_closest_points(points, (0, 0), 3))
# Expected output: [(-1, 0), (0, -1), (1, 0)]

When Binary Search Applies

A linear scan costs O(nd) because there is no inherent sorted order for arbitrary multidimensional points. Binary search costs O(log n) only when searching sorted scalar keys or a monotonic condition; computing distances for unsorted points still requires O(nd) work.

For a sorted list of scalar distances, bisect_left and bisect_right provide lower and upper bounds, which can also locate the first and last occurrence of a distance. Searching a rotated sorted array and binary search on a monotonic answer are specialized techniques and do not directly solve general k-nearest-point selection.

Common Pitfalls

  • Off-by-one errors: Check whether the heap contains exactly k elements before accessing or replacing its root.

  • Input mutation: Do not remove points from the original list; use a separate heap.

  • Duplicate distances: Either duplicate point is valid when distances tie; the implementation orders equal-distance points lexicographically.

  • Invalid dimensions: Ensure every point has the same number of coordinates as the origin.

  • Empty input: With no points, k = 0 returns an empty list, while any positive k raises ValueError.

  • One-point input: With one point, k = 1 returns that point, while k > 1 raises ValueError.

  • Negative coordinates: Negative coordinates and zero are handled normally.

  • Input order: Already sorted and unsorted inputs behave identically because every point is scanned, and the input is not mutated.

  • Integer overflow: In languages such as Java or C++, use sufficiently wide integer types when squaring large coordinates.

43

How does search engine indexing use search algorithms?

Search engine indexing creates a structured representation of crawled documents—usually an inverted index—so queries can locate relevant pages without scanning every original document. Search algorithms then help retrieve candidate documents and rank them efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Indexing Process Works

  1. Crawling: Search engine crawlers discover URLs and download accessible pages.

  2. Parsing and extraction: The crawler removes markup, identifies headings and body content, and extracts text, links, and metadata.

  3. Tokenization: Text is split into tokens, usually words and phrases.

  4. Normalization: Tokens are lowercased, stemmed or lemmatized, and sometimes synonym-expanded. Stop words may be removed.

  5. Indexing: Each term is associated with the documents containing it. A term such as python might map to a posting list containing document IDs and optional term frequencies or positions.

  6. Segment publication: Index partitions are stored and made available to query-serving systems, often with replicas and compression.

For a corpus containing T token occurrences and P postings, indexing generally takes O(T) average time with hash-based term dictionaries. The index occupies O(V + P) space, where V is the vocabulary size; the original corpus is not counted as index storage.

How Search Algorithms Are Used

A query is parsed and normalized, then candidate-generation algorithms use the inverted index to find documents containing relevant terms. Posting-list intersections can combine results for multiple terms, while ranking algorithms such as BM25 score the candidates.

Searching algorithms also operate inside individual components:

  • Hash-table lookup: Finds a term’s posting list in O(1) average time and O(n) worst time because of collisions.

  • Binary search: Finds a document ID or posting boundary in O(log n) time when the values are sorted.

  • Prefix search: Tries or prefix-based indexes locate terms beginning with a query prefix in time proportional to the prefix length.

  • Top-k selection: Ranking systems can use heaps to retain the highest-scoring candidates in O(m log k) time for m candidates and a result size of k.

Approach Best time Average time Worst time Auxiliary space Appropriate use
Linear search O(1) O(n) O(n) O(1), excluding input Small or unsorted collections
Binary search O(1) O(log n) O(log n) O(1), excluding input; no recursion stack Sorted data or a monotonic condition
Hash-table lookup O(1) O(1) O(n) O(n) for the table Term dictionaries
Inverted-index lookup — Proportional to matching postings Proportional to matching postings O(V + P) for the index Full-text retrieval

Important binary-search variants include:

  • First or last occurrence: Use lower and upper bounds to handle duplicates.

  • Lower and upper bound: Python provides bisect_left and bisect_right for sorted lists.

  • Rotated sorted array: A modified binary search achieves O(log n) with distinct values; duplicates can degrade it to O(n).

  • Binary search on the answer: Find a minimum capacity, threshold, or integer square root by binary-searching a monotonic predicate over a numeric range.

Common Pitfalls

  • Unsorted input: Ordinary binary search is invalid unless the data is sorted or the predicate is monotonic.

  • Empty or single-element input: Empty input should return no match or the insertion boundary; a one-element list requires only one comparison.

  • Duplicates: Exact binary search may return any duplicate. Use lower and upper bounds for predictable first and last positions.

  • Negative numbers: Standard comparisons handle negatives without special treatment.

  • Off-by-one errors: Decide explicitly whether the interval is [lo, hi] or [lo, hi).

  • Mutation: Avoid changing the input during a search unless the algorithm explicitly permits it.

  • Graph indexing: Graph crawlers need a visited set to prevent cycles and must handle disconnected components.

  • Recursion depth: Recursive graph traversal can exceed Python’s default recursion limit; an explicit stack is safer for large or deeply nested graphs.

44

How do you find an item matching multiple search criteria?

Multi-criteria search usually combines the requirements into one Boolean predicate and scans the collection until a match is found. Use binary search only when the collection is sorted and that predicate has a monotonic transition from false to true.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How to Combine Criteria

Express each requirement as a condition and combine them with logical AND:

  • Category condition: the item belongs to the required category.

  • Threshold condition: its price or score falls within the allowed range.

  • State condition: it is active, available, or otherwise eligible.

The general pattern is:

item matches if criterion_1 and criterion_2 and criterion_3

For an unsorted collection, use a linear search. The scan checks items in their original order and stops at the first item satisfying every condition. This is also the most reliable approach when the criteria are arbitrary.

Linear Search vs Binary Search

Approach Best time Average time Worst time Auxiliary space When to use
Linear search O(1) O(n) O(n) O(1) Unsorted data or arbitrary criteria
Binary search O(1) O(log n) O(log n) O(1) Sorted data with a monotonic predicate
  • Linear search reason: it may inspect every element before determining that no match exists.

  • Binary search reason: each comparison eliminates half of the remaining search interval.

  • Space is O(1) auxiliary for both approaches; the input is not counted, and neither implementation requires a recursion stack.

  • If all matching items are collected rather than just the first, the result requires O(k) space for k matches, while the scan itself still uses O(1) auxiliary space.

Binary search is invalid merely because some fields happen to be sorted. For example, filtering books under a price limit is not necessarily monotonic if prices or categories are interleaved.

Code Example

from collections.abc import Callable
from dataclasses import dataclass
from typing import TypeVar

T = TypeVar("T")


@dataclass(frozen=True)
class Product:
    name: str
    category: str
    price: int
    in_stock: bool
    published_year: int


def find_first(
    items: list[T],
    predicate: Callable[[T], bool],
) -> T | None:
    """Return the first item satisfying every criterion, or None."""
    for item in items:
        if predicate(item):
            return item
    return None


def find_first_monotonic(
    items: list[T],
    predicate: Callable[[T], bool],
) -> T | None:
    """Return the first match where the predicate changes from False to True."""
    lo, hi = 0, len(items) - 1  # Inclusive interval [lo, hi]
    ans = None
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if predicate(items[mid]):
            ans = items[mid]
            hi = mid - 1
        else:
            lo = mid + 1
    return ans


products = [
    Product("Notebook", "stationery", 5, True, 2021),
    Product("Dune", "book", 18, True, 1965),
    Product("Hobbit", "book", 15, True, 1937),
    Product("Clean Code", "book", 30, True, 2008),
]

# Linear search with multiple criteria
result = find_first(
    products,
    lambda item: (
        item.category == "book"
        and item.price <= 20
        and item.in_stock
    ),
)
print(result)
# Product(name='Dune', category='book', price=18, in_stock=True, published_year=1965)

# Binary search requires a monotonic predicate; here we use only published_year
chronological = sorted(products, key=lambda item: item.published_year)
result = find_first_monotonic(
    chronological,
    lambda item: item.published_year >= 2000,
)
print(result)
# Product(name='Clean Code', category='book', price=30, in_stock=True, published_year=2008)

The mid = lo + (hi - lo) // 2 calculation avoids overflow caused by adding two large indices in languages with fixed-width integers.

Step-by-Step Trace

For the linear search, the predicate requires a book costing at most 20 and currently in stock:

  1. Notebook fails because its category is stationery.

  2. Dune passes all three conditions, so it is returned immediately.

  3. The remaining products are not examined.

Related Search Variants

  • First or last occurrence: For a sorted exact key, find the lower and upper boundaries and select the first or last item in that range.

  • Lower and upper bound: Python’s bisect_left and bisect_right locate insertion boundaries in a sorted list. They apply to one ordering key, not arbitrary multi-criteria predicates.

  • Rotated sorted array: Binary search can locate a match after first identifying the rotation point, provided records remain ordered by the same key.

  • Binary search on the answer: Search a numeric range when a feasibility function incorporating all constraints changes monotonically, such as finding the minimum capacity that can ship all orders.

Common Pitfalls

  • Returning the first partial match instead of requiring every condition to pass.

  • Assuming binary search works on sorted input without checking predicate monotonicity.

  • Using off-by-one boundaries; the example explicitly searches the inclusive interval [lo, hi].

  • Mutating the input unnecessarily; the example preserves the original order.

  • Handling duplicates incorrectly: find_first returns the earliest matching element, while bisect_left and bisect_right identify a range of equal keys.

  • Empty input returns None, one-element input works normally, and negative values work because comparisons are not tied to a particular sign.

  • Already sorted input does not change linear-search complexity; disconnected graphs and cycles are not applicable to this array-search operation.

  • Interviewers commonly follow up by asking whether to return one match or all matches, whether the data is sorted, and how the solution changes for a very large collection.

45

How do unique constraints change database search algorithms?

A unique constraint turns a search by that key into an identity lookup: the key identifies either zero or one row. With a supporting index, the database can seek directly to the matching row instead of scanning for and removing duplicates.

Read full answer

Applies tolanguage-independent

How the Adaptation Works

  • Search the unique key directly: Use an equality predicate such as WHERE email = ? rather than retrieving every row and deduplicating them in application code.

  • Enforce uniqueness in the database: Check constraints when writes occur, not only through a preceding search. A “search, then insert” sequence can race with another transaction.

  • Use the same expression for indexing and querying: For example, if uniqueness is case-insensitive, normalize the value before both insertion and lookup, or use an engine-supported functional or expression index.

  • Understand composite uniqueness: A constraint on (tenant_id, account_number) guarantees one row for that combination, but searching by account_number alone may still return multiple rows.

  • Handle nullable columns carefully: Most databases allow multiple NULL values in a unique column because NULL is not considered equal to another NULL.

Complexity and Search Variants

Approach Best Average Worst Space When to Use
Linear search O(1) O(n) O(n) O(1) auxiliary Small or unsorted data
Binary search O(1) O(log n) O(log n) O(1) auxiliary Sorted, unique keys (in-memory)
Indexed database equality lookup O(1) O(log n) O(log n) O(n) persistent index Normal production lookup

The manual complexities count only auxiliary space; the input list or table is not counted. A database index normally requires O(n) persistent storage, while exact query-memory usage is engine-dependent.

  • First and last occurrence: With unique keys, they are the same row.

  • Lower and upper bound: In a sorted unique collection, bisect_right is exactly one more than bisect_left when the key is present; the two are equal only when the key is absent.

  • Rotated sorted array: Uniqueness removes duplicate ambiguity, but rotated arrays are uncommon as database indexes; ordinary indexes remain sorted.

  • Binary search on the answer: This is unrelated to identity lookup. It is appropriate for a monotonic condition such as minimum shipping capacity.

Practical Design Guidance

  • Use atomic conflict handling: Prefer database-specific UPSERT, ON CONFLICT, or ignore-conflict behavior according to the required semantics. Do not rely on a separate SELECT before inserting.

  • Avoid unnecessary LIMIT 1: A unique equality lookup already returns at most one row. LIMIT 1 does not enforce uniqueness and may hide incorrect schema design.

  • Check the query plan: Confirm that the optimizer uses the intended index rather than performing a full table scan.

  • Preserve search semantics: A case-sensitive unique index does not automatically support case-insensitive searches.

Common Pitfalls

  • Assuming uniqueness applies to only part of a composite key.

  • Allowing multiple NULL values unintentionally.

  • Comparing normalized values differently during insertion and searching.

  • Using a leading wildcard such as email LIKE '%example.com', which usually prevents an efficient index seek.

  • Checking for duplicates only in application code, which can fail under concurrent writes.

46

What problems occur in recursive binary search implementations?

Recursive binary search commonly fails because of incorrect boundary handling, an unsorted input, or a recursive call that does not strictly reduce the search interval. A correct implementation must also define how duplicates and missing values are represented.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a sorted array, binary search repeatedly examines the middle element:

  1. If it equals the target, return its index.

  2. If it is smaller, search the right half.

  3. If it is larger, search the left half.

  4. Stop when the search interval becomes empty.

An inclusive search uses the interval [lo, hi] and calculates the midpoint as mid = lo + (hi - lo) // 2. In fixed-width languages, this avoids overflow that can occur when calculating (lo + hi) // 2 with very large indices. Python integers do not overflow, but the same formula is portable.

Example trace for [-8, -2, 0, 4, 7, 11] and target 7:

Step Interval Midpoint Value Action
1 [0, 5] 2 0 Search right
2 [3, 5] 4 7 Found

Potential Issues

  • Unsorted input: Binary search is valid only when values are sorted, or when a separate monotonic condition guarantees which half can be discarded.

  • Incorrect base case: The empty interval is lo > hi for an inclusive search. An exclusive interval uses lo >= hi.

  • Off-by-one errors: In an inclusive search, the next intervals are [mid + 1, hi] and [lo, mid - 1]. Retaining mid in the relevant recursive call can prevent the interval from shrinking.

  • Overflow risk: In languages such as Java or C++, lo + hi may overflow before division.

  • Duplicate values: Exact-match binary search may return any occurrence, not necessarily the first or last. Lower-bound and upper-bound variants provide deterministic positions.

  • Unclear return value: Returning -1 is conventional for a missing target, but the function should document this behavior.

  • Accidental slicing: Operations such as values[mid + 1:] copy portions of the list. On a normal single-branch recursive search, copying at every level can reduce time to O(n) and increase extra space to O(n), eliminating binary search’s usual advantages.

  • Mutating the input: Binary search does not require mutation, so the original collection should remain unchanged.

  • Wrong ordering assumption: An ascending implementation cannot correctly search a descending array unless the comparisons are reversed.

Edge cases include empty and one-element collections, duplicate values, negative values, already sorted input, and missing targets. Empty input terminates immediately, while duplicate values are valid but require a first- or last-occurrence variant when that distinction matters.

Complexity

Approach Best time Average time Worst time Extra space When to use
Linear search O(1) O(n) O(n) O(1) Small, unsorted, or occasionally updated collections
Recursive binary search O(1) O(log n) O(log n) O(log n) recursion stack Random-access data that is sorted or has a monotonic condition

The search performs O(log n) comparisons because each recursive call halves the remaining interval. The extra space is O(log n) in the worst case because recursive calls remain on the call stack. The input collection is not counted as extra space.

Common Variants

  • First and last occurrence: Use lower-bound and upper-bound logic to find the beginning and end of a range containing duplicates. Both require O(log n) time and O(log n) recursive stack space, or O(1) extra space when implemented iteratively.

  • Lower and upper bounds: Python provides bisect_left and bisect_right for ascending sorted lists. Both run in O(log n) time with O(1) extra space.

  • Rotated sorted array: With distinct elements, compare the midpoint against a sorted endpoint to determine which half is ordered. This takes O(log n) time, with O(log n) recursive stack space or O(1) iterative space. Duplicates can make the worst case O(n) time and, for recursive approaches, potentially O(n) stack space.

  • Binary search on an answer: To find a minimum feasible capacity, the feasibility predicate must be monotonic from false to true. Searching a range of size R makes O(log R) predicate calls. If each predicate evaluation costs T, total time is O(T log R), with O(1) search bookkeeping space excluding the predicate’s own requirements.

  • Exact match versus insertion point: Exact-match search returns a matching index or -1; lower-bound search returns the position where a value would be inserted while preserving ascending order.

Common Pitfalls

  • Mixing inclusive [lo, hi] and exclusive [lo, hi) boundaries.

  • Using lo = mid or hi = mid, which may not reduce the interval.

  • Forgetting that the input must be sorted.

  • Assuming the first returned index is the first duplicate.

  • Using floating-point midpoints, which can introduce rounding errors in some languages.

  • Creating slices during recursion and unintentionally increasing complexity.

  • In an iterative implementation, forgetting that hi = mid - 1 is required for an inclusive interval.

Interviewers commonly follow up by asking how to find the first or last duplicate, how to determine an insertion point, and how binary search could find the minimum value satisfying a monotonic condition.

47

How do recursive and iterative search algorithms compare?

Recursive search calls itself with a smaller problem, while iterative search uses a loop and explicit index variables. They generally have the same time complexity, but recursion consumes call-stack space; iterative implementations usually require O(1) extra space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Recursive implementation: Each call stores parameters and intermediate state on the call stack. It can read naturally, but excessive recursion may exceed Python’s default recursion limit of about 1,000 calls.

  • Iterative implementation: A while loop maintains the search state explicitly. It is usually easier to analyze, debug, and run on very large inputs.

  • The algorithm determines the time complexity; recursion versus iteration primarily affects stack usage.

For values = [-4, 1, 3, 6, 9] and target = 3:

  1. Linear search checks indices 0, 1, and 2, then returns 2.

  2. Binary search starts with lo = 0, hi = 4, and mid = 2.

  3. Because values[2] == 3, it immediately returns 2.

Complexity Comparison

Approach Best time Average time Worst time Extra space
Linear, iterative O(1) O(n) O(n) O(1)
Linear, recursive O(1) O(n) O(n) O(n)
Binary, iterative O(1) O(log n) O(log n) O(1)
Binary, recursive O(1) O(log n) O(log n) O(log n)
  • Linear search requires O(n) time because it may inspect every element. Recursion adds an O(n) stack in the worst case.

  • Binary search requires O(log n) time because it halves the remaining interval. Recursion adds an O(log n) stack.

  • Space excludes the input list but includes the recursion stack.

Variants and Preconditions

  • First or last occurrence: Binary-search the left or right half after finding a match, remaining O(log n).

  • Lower and upper bounds: Python’s bisect_left and bisect_right find insertion boundaries in a sorted list in O(log n) time and O(1) extra space.

  • Rotated sorted array: Identify the rotation point and search the valid half in O(log n) time. With duplicates, the worst case can degrade to O(n).

  • Binary search on the answer: Search a numeric range using a monotonic predicate, such as whether capacity is sufficient for a demand. This requires O(log n) predicate evaluations, each with its own cost.

  • Exponential search: Finds an item in an unbounded sorted sequence by doubling the range, requiring O(log n) comparisons.

  • Interpolation search: Uses value-based estimates and takes O(log log n) average time on uniformly distributed data, but O(n) in the worst case.

Common Pitfalls

  • Using lo <= hi with an inclusive interval, or mixing inclusive and exclusive boundaries, causes off-by-one errors.

  • Calculating mid as (lo + hi) // 2 can overflow in fixed-width languages such as Java or C++; use lo + (hi - lo) // 2.

  • Forgetting that binary search requires sorted input or a monotonic predicate.

  • Mutating the input while searching can invalidate the search order.

  • Using recursive linear search on more than roughly 1,000 elements can raise RecursionError.

  • Interviewers commonly ask about stack depth, duplicate handling, and how to find the first or last occurrence.

48

When is iterative searching preferable to recursive searching?

Iterative searching is often preferable to recursive searching when avoiding call-stack growth, reducing stack memory, or controlling execution explicitly matters. For binary search, an iterative implementation uses O(1) auxiliary space, while the recursive version uses an O(log n) recursion stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Iterative Searching Helps

  • Avoiding recursion-depth limits: A recursive binary search normally has only O(log n) depth, so it is rarely affected by Python’s roughly 1,000-call default limit. Iterative implementations are still safer for algorithms or tree structures that can become deeply nested.

  • Reducing stack usage: An iterative binary search needs only a few variables, whereas recursive search must preserve a stack frame for each pending call.

  • Explicit control flow: Iteration makes it easier to pause, resume, instrument, or trace each search step.

  • Lower overhead in tight loops: Avoiding function-call and return overhead can improve constant-factor performance, although the asymptotic complexity remains the same.

  • Handling large or streaming inputs: An iterative search can process available elements without creating a recursive call stack. This is especially useful when search state must be maintained between batches.

Recursion can still be clearer for naturally recursive problems, such as divide-and-conquer algorithms or searching recursively defined tree structures.

Complexity Comparison

Auxiliary space below excludes the input itself but includes any recursion stack.

Approach Best time Average time Worst time Auxiliary space Reason
Linear search O(1) O(n) O(n) O(1) May inspect every element; can succeed immediately
Iterative binary search O(1) O(log n) O(log n) O(1) Halves the search interval each step
Recursive binary search O(1) O(log n) O(log n) O(log n) Call stack grows with search depth

Binary search requires sorted data or another monotonic condition. Linear search works with unsorted data but can require O(n) comparisons in the worst case.

Example Walkthrough

Using an inclusive interval [lo, hi], calculate mid = lo + (hi - lo) // 2. Unlike lo + hi, this midpoint calculation avoids integer overflow in languages with fixed-width integers.

For [1, 3, 3, 5, 7] and a target of 5:

  1. The initial interval is [0, 4], so mid = 2; values[2] is 3, which is too small.

  2. The new interval is [3, 4], so mid = 3; values[3] is 5.

  3. The target is found at index 3.

A correct binary-search implementation must define behavior for an empty list, a one-element list, duplicates, negative numbers, and already sorted input. It should return one matching index when duplicates exist unless first or last occurrence is requested.

Search Variants and Edge Cases

Variant Behavior Typical implementation
First occurrence Finds the earliest matching index After a match, continue searching the left half
Last occurrence Finds the final matching index After a match, continue searching the right half
Lower bound Finds the first index whose value is at least the target Use bisect_left in Python
Upper bound Finds the first index whose value is greater than the target Use bisect_right in Python
Rotated sorted array Searches a sorted array rotated around one pivot Adjust the interval after comparing the pivot with the target
Binary search on the answer Searches over a numeric answer space Use a monotonic feasibility condition

A single midpoint match is insufficient when first or last occurrence is required. A rotated sorted array requires a modified binary search because one half may not be sorted. Binary search on an answer requires a monotonic predicate; for example, capacity is feasible for all larger capacities.

Common Pitfalls

  • Using binary search on unsorted data: Results are incorrect unless the data is sorted or a monotonic condition is being searched.

  • Incorrect interval updates: The usual pattern is lo = mid + 1 or hi = mid - 1; repeating the midpoint can cause an infinite loop.

  • Confusing bounds: bisect_left finds the insertion position before equal values, while bisect_right finds the position after them.

  • Ignoring duplicates: A standard binary search may return any matching index, not necessarily the first or last.

  • Assuming iteration always saves memory: If an iterative algorithm uses an explicit stack, its space may be O(n), the same as recursion.

  • Mutating the input unnecessarily: Keep the original collection unchanged unless the operation explicitly permits mutation.

49

How should sparse datasets guide search algorithm selection?

Search strategy should be selected from the query pattern, data ordering, query frequency, and available memory—not from sparsity alone. A sparse dataset usually contains fewer occupied values than its logical universe, so a compact representation combined with linear search, binary search, hashing, or bounds search can avoid processing absent entries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Choosing an Algorithm

  • One or a few exact-match queries over unsorted data: Use linear search. It requires O(n) worst-case time but only O(1) auxiliary space.

  • Many repeated exact-match queries: Build a hash-based dictionary mapping each occupied value to an index. Building it costs expected O(n) time, and each lookup takes O(1) time on average.

  • Sorted data or range and nearest-value queries: Sort the occupied values once, then use binary search, bisect_left, and bisect_right.

  • Already sorted data with many queries: Skip the sort and use binary search directly.

  • Sparse matrices or sparse maps: Represent occupied coordinates as dictionary keys, such as (row, column), instead of allocating entries for absent coordinates.

  • Monotonic feasibility problems: Use binary search on the answer when a feasibility predicate has a consistent monotonic transition, such as false to true.

Sparsity describes the representation, not the search algorithm. For example, twenty occupied values in a universe of one billion values should generally remain compact rather than being expanded into one billion placeholders.

Complexity Comparison

Here, n is the number of occupied values and q is the number of queries. Auxiliary space excludes the original input and returned results. All algorithms are iterative, so their recursion-stack usage is O(1).

Approach Best query time Average query time Worst query time Auxiliary space Use when
Linear search O(1) O(n) O(n) O(1) Unsorted data or very few queries
Binary membership search O(1) O(log n) O(log n) O(1) Data is already sorted
Hash-table lookup O(1) O(1) O(n) O(n) for the index Many exact-match queries
Sorted values plus bounds search O(log n) O(log n) O(log n) O(n) for a sorted copy Range, nearest-value, or occurrence queries

Preprocessing must also be included:

  • Hash index: Expected O(n) construction time and O(n) worst-case construction time for a conventional chained hash table. Thus, q lookups cost O(n + q) expected time and O(n² + qn) in the worst case.

  • Sorting once: Best-case O(n) when input is already sorted; average and worst case O(n log n). After sorting, q bounds searches cost O(q log n), making the total O(n + q log n) for already sorted input and O(n log n + q log n) otherwise.

Binary Search Variants

  • Membership search: Compare the middle value with the target and discard one half.

  • Lower bound: Find the first position whose value is at least the target; Python provides bisect_left.

  • Upper bound: Find the first position whose value is greater than the target; Python provides bisect_right.

  • First and last occurrence: Use the lower bound and upper bound. The last occurrence is the upper-bound position minus one when the target exists.

  • Rotated sorted array: Identify the sorted half before searching it. The standard algorithm for a rotated array with distinct values takes O(log n) time and O(1) auxiliary space.

  • Binary search on the answer: Search a monotonic candidate range in O(log R) predicate checks, where R is the range size, plus the cost of each check.

For an inclusive interval, use low, high, and mid = low + (high - low) // 2. Subtracting before dividing avoids overflow in fixed-width languages when the difference is representable.

Practical Example

Suppose a sparse dataset contains the occupied values [10, 20, 70], and the queries are 20 and 60.

  1. For only one exact-match query, linear search checks occupied values directly and uses O(n) worst-case time with O(1) auxiliary space.

  2. For many repeated exact-match queries, build an index such as {10: 0, 20: 1, 70: 2} in expected O(n) time, then resolve each query in O(1) average time.

  3. For range queries, sort the occupied values once and use lower and upper bounds to find the positions matching each range.

Common Pitfalls

  • Choosing by sparsity alone: Query type, ordering, frequency, and memory constraints determine the algorithm.

  • Unsorted binary search: Binary search is invalid unless the data is sorted or the searched condition is monotonic.

  • Ignoring preprocessing: Hash indexing and sorting add time and memory that must be compared with the expected query savings.

  • Hash collisions: Average O(1) lookup becomes O(n) in the worst case for a particular lookup.

  • Duplicate values: Decide whether any match, the first match, the last match, or every match is required.

  • Edge cases: Empty input returns no matches; one-element inputs work normally; negative values require no special handling for comparisons.

  • Mutating input: Use a sorted copy when the original ordering must remain unchanged.

50

How does sorted versus unsorted data affect search algorithm selection?

Sorted data enables binary search, reducing the number of comparisons from linear to logarithmic. With unsorted data, linear search is the reliable default unless sorting the data or using a different searchable structure provides a better overall tradeoff.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Tradeoff

  • Unsorted data: Linear search checks elements sequentially until it finds the target or exhausts the collection.

  • Sorted data: Binary search repeatedly eliminates half of the remaining search interval.

  • Random-access requirement: Binary search requires direct indexing. It is suitable for arrays and lists, but not ordinary linked lists.

  • Ordering requirement: Binary search requires a consistent ascending or descending ordering. It cannot be applied directly to arbitrary unsorted data.

Complexity Comparison

Approach Best Average Worst Auxiliary Space
Linear search O(1) O(n) O(n) O(1)
Binary search O(1) O(log n) O(log n) O(1) iterative
Recursive binary search O(1) O(log n) O(log n) O(log n) recursion stack
  • Reason for linear search time: In the worst case, every element is inspected.

  • Reason for binary search time: Each comparison discards approximately half of the remaining interval.

  • Space accounting: These are auxiliary-space bounds and do not count the input array itself. If the input is counted, storing n elements requires O(n) total space.

  • Duplicate behavior: A basic binary search may find any occurrence of a duplicated target. Finding the first or last occurrence requires additional boundary logic.

Choosing an Algorithm

  • One search over unsorted data: Use linear search. Sorting first costs O(n log n), so it is unlikely to help for only one lookup.

  • Many searches over the same data: Sort once in O(n log n), then perform each binary search in O(log n).

  • Already sorted data: Use binary search immediately.

  • Data becomes unsorted between searches: Maintain sorted order, or return to linear search.

  • Large data with frequent insertions and deletions: Sorting after every change can be expensive, so the cost of maintaining sorted order must be included in the design.

The key decision is not merely the size of the collection but whether ordering is already available and whether the total cost of creating that ordering is justified.

Binary Search Variants

  • First occurrence: Use binary search to find the target, then continue searching left until an element before the matching range is reached.

  • Last occurrence: Locate the target and continue searching right.

  • Lower bound: bisect_left in Python returns the insertion position before any existing equal elements.

  • Upper bound: bisect_right returns the insertion position after all existing equal elements.

  • Rotated sorted array: A modified binary search can locate a target in O(log n) for a rotated array with distinct elements by determining which half remains sorted and whether the target falls within that half. With duplicates, extra care is required and the worst case can degrade to O(n).

  • Binary search on the answer: If a predicate is monotonic, such as “can all items be shipped with capacity c?”, binary search the predicate’s answer space rather than an explicitly sorted array.

Example Trace

For values = [3, 8, 15, 22, 27] and target 22:

  1. Linear search examines indices 0, 1, 2, and 3, making four comparisons.

  2. Binary search begins with lo = 0, hi = 4, and mid = 2.

  3. The value at index 2 is 15; because 22 > 15, set lo = 3.

  4. Now lo = 3, hi = 4, and mid = 3.

  5. The value at index 3 is 22, so the search succeeds.

Common Pitfalls

  • Using binary search on unsorted data can incorrectly discard the half containing the target.

  • Decide whether the interval is inclusive, [lo, hi], or half-open, [lo, hi), and remain consistent.

  • Prefer mid = lo + (hi - lo) // 2; this avoids overflow in fixed-width languages when lo + hi is too large.

  • Include duplicate-handling requirements in the design: any occurrence, first occurrence, last occurrence, or count.

  • Do not ignore the O(n log n) cost of sorting when comparing strategies.

  • Interviewers commonly ask why binary search is invalid for unsorted data, how the midpoint is calculated, and how the first occurrence of a duplicate is found.

51

How do you search datasets with periodic patterns or anomalies?

Use structure-aware searching: exploit sorted or periodic structure when it is guaranteed, and scan against an expected baseline when looking for anomalies. The correct algorithm depends on whether the dataset is sorted, repeated in blocks, or only approximately predictable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Choosing a Search Strategy

Approach Best Average Worst Auxiliary Space When to Use
Linear search O(1) O(n) O(n) O(1) Unsorted data or no useful structure
Binary search O(1) O(log n) O(log n) O(1) Sorted data or a monotonic condition
Search repeated sorted blocks O(⌈n/p⌉ log(p + 1)) Same Same O(1) Data is divided into sorted periods of length p
Search one known repeated block O(log(p + 1) + k) Same Same O(1) Every complete block is identical and trusted
Periodic anomaly scan O(n) O(n) O(n) O(1) Values are expected to repeat every p positions
Rolling-window scan, recomputing each window O(nw) O(nw) O(nw) O(w) General numerical series with local baselines

Here, n is the number of elements, p is the period, w is the window size, and k is the number of returned matches. Linear search examines up to n elements; binary search repeatedly halves a sorted interval. Searching ⌈n/p⌉ blocks requires one binary search per block. A periodic scan must inspect every element, making O(n) necessary when every element must be classified. Recomputing a window costs O(w) per position; a rolling sum can reduce mean-based detection to O(n), while a rolling median using two heaps costs O(n log w).

Space figures exclude the input and returned output; output requires O(k) or O(a) space for k matches or a anomalies. No recursion stack is used.

Periodic Patterns and Anomalies

For repeated sorted blocks, search each block with binary search. For example, data divided into periods of three can be searched independently in each block. If all complete blocks are guaranteed identical, search one block and map its relative position into every complete block; a partial final block must be handled separately.

For periodic anomalies, use the first period as a baseline and compare each value with the expected value at the same phase:

values[i] != values[i % period]

This is effective when the baseline is trustworthy. A contaminated baseline can incorrectly flag valid repetitions, while anomalies within the first period cannot be detected relative to that same baseline. If period is at least the dataset length, no phase has a later observation, so no repetition violation can be established.

Example:

Index 0 1 2 3 4 5 6 7
Actual 1 4 8 1 4 8 1 99
Expected 1 4 8 1 4 8 1 4
Result OK OK OK OK OK OK OK Anomaly

Related Binary-Search Variants

Variant Method Complexity
First-occurrence candidate bisect_left(target) O(log n)
Last-occurrence candidate bisect_right(target) - 1 O(log n)
Occurrence count bisect_right(target) - bisect_left(target) O(log n)
Rotated sorted array Find the pivot, then search the valid sorted half O(log n) for distinct values
Binary search on an answer Binary-search the smallest value satisfying a monotonic test O(T log R)

After calling bisect_left or bisect_right, check that the candidate index is within bounds and that the value equals the target. For binary search on an answer, R is the number of candidate values and T is the cost of one feasibility test. The condition must be monotonic: if capacity c works, every larger capacity also works. With an O(n) test, the total is O(n log R). Searching a rotated array with duplicates can degrade toward O(n).

Code Example

from collections.abc import Sequence


def search_sorted_blocks(
    values: Sequence[int], target: int, period: int
) -> list[int]:
    """Return one target index from each sorted block of the given period."""
    if period <= 0:
        raise ValueError("period must be positive")

    matches: list[int] = []

    for block_start in range(0, len(values), period):
        lo = block_start
        hi = min(block_start + period, len(values)) - 1

        # Search the inclusive interval [lo, hi].
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            value = values[mid]

            if value == target:
                matches.append(mid)
                break
            if value < target:
                lo = mid + 1
            else:
                hi = mid - 1

    return matches


def find_periodic_anomalies(
    values: Sequence[int], period: int
) -> list[int]:
    """Return indices that violate repetition of the first period."""
    if period <= 0:
        raise ValueError("period must be positive")

    anomalies: list[int] = []

    for index, value in enumerate(values):
        if value != values[index % period]:
            anomalies.append(index)

    return anomalies


values = [1, 4, 8, 1, 4, 8, 1, 99]
print(search_sorted_blocks(values, target=4, period=3))  # [1, 4]
print(find_periodic_anomalies(values, period=3))        # [7]

The midpoint formula lo + (hi - lo) // 2 avoids overflow when lo + hi exceeds a fixed-width integer in languages such as Java or C++, although Python integers do not overflow.

Interview Tips

  • Verify preconditions: Binary search requires each searched block to be sorted.

  • Handle duplicates: Use lower and upper bounds when every occurrence is required.

  • Do not mutate input: Sorting an unsorted dataset first costs O(n log n).

  • Distinguish matching from anomaly detection: A value can match a searched pattern while still violating an expected baseline.

  • Mention edge cases: Empty input, one element, duplicate values, negative numbers, partial final periods, incomplete baselines, and contaminated baselines.

52

How do you customize binary search to find the closest value?

Lower-bound binary search finds the closest value by locating the first element greater than or equal to the target. The two candidates are that element and its predecessor, so comparing their distances from the target is sufficient.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an ascending sorted array, binary search maintains an insertion index using the half-open interval [lo, hi):

  1. Calculate mid = lo + (hi - lo) // 2.

  2. If values[mid] < target, the insertion point must be after mid.

  3. Otherwise, mid may be the insertion point, so search the left half.

  4. When the search finishes, lo is the lower-bound index.

  5. Compare values[lo] with values[lo - 1] and return whichever is closer.

The midpoint formula avoids addition overflow in fixed-width languages such as Java and C++. Python integers do not overflow, but the same formula remains portable.

If the target is outside the array’s range, return the first or last element. For equal distances, this implementation returns the lower value.

Binary Search Variants

Variant Technique Time Auxiliary space
First occurrence Use bisect_left; it is the first exact match when the value exists O(log n) O(1)
Last occurrence Use bisect_right(values, target) - 1 when the target exists O(log n) O(1)
Lower bound First index whose value is at least the target, equivalent to bisect_left O(log n) O(1)
Upper bound First index whose value is greater than the target, equivalent to bisect_right O(log n) O(1)
Rotated sorted array Use modified comparisons that account for the rotation O(log n) for distinct values; O(n) worst case with duplicates O(1)
Binary search on an answer Search for the first satisfying point of a monotonic predicate O(log R), where R is the search range O(1)

Binary search on an answer is used for problems such as minimum ship capacity or minimum square root, where feasibility is monotonic rather than the input being sorted.

Complexity

Approach Best time Average time Worst time Extra space When to use
Linear scan O(1) O(n) O(n) O(1) Unsorted data or very small arrays
Lower-bound binary search O(log n) O(log n) O(log n) O(1) Ascending sorted data or an equivalent monotonic condition

A linear scan visits elements one at a time, while binary search repeatedly halves the remaining interval. Both use O(1) auxiliary space because they retain only a few variables. The input array is excluded from this count; including it would make total space O(n).

Edge Cases and Walkthrough

  • Empty array: Return None.

  • One element: Return that element.

  • Duplicates: Return the same closest value; the lower-value tie rule still applies.

  • Negative numbers: Comparisons and distance calculations work normally.

  • Target outside the range: Return the nearest boundary.

  • Sorted input: The algorithm does not modify or sort it.

  • Ties: Return the smaller value deterministically.

For values = [1, 4, 8, 13] and target = 10:

  1. Binary search finishes with lo = 3.

  2. The value at the lower-bound index is 13, at distance 3.

  3. Its predecessor is 8, at distance 2.

  4. The function returns 8.

Code Example

from collections.abc import Sequence


def closest_value(values: Sequence[float], target: float) -> float | None:
    """Return the closest value, preferring the lower value on ties."""
    if not values:
        return None

    lo, hi = 0, len(values)

    # Find the first index whose value is >= target in [lo, hi).
    while lo < hi:
        mid = lo + (hi - lo) // 2

        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid

    if lo == 0:
        return values[0]
    if lo == len(values):
        return values[-1]

    upper_candidate = values[lo]
    lower_candidate = values[lo - 1]

    if target - lower_candidate <= upper_candidate - target:
        return lower_candidate

    return upper_candidate


values = [1, 4, 8, 13]
print(closest_value(values, 10))  # 8

Common Pitfalls

  • Off-by-one errors: Carefully maintain either [lo, hi) or [lo, hi]; this implementation uses [lo, hi) and therefore assigns hi = mid.

  • Integer overflow: In Java and C++, computing lo + hi can overflow; use lo + (hi - lo) // 2.

  • Using binary search on unsorted data: The lower-bound position is undefined unless the data is sorted or the comparison follows a monotonic condition.

  • Selecting only one candidate: Both the lower bound and its predecessor may be closer.

  • Ignoring duplicates: Use bisect_left for the first occurrence and bisect_right - 1 for the last when the target exists.

  • Leaving tie behavior undefined: State whether the lower or higher value wins.

  • Mutating the input: The implementation preserves the caller’s array.

Common interview follow-ups include finding the first and last occurrence, returning the index instead of the value, handling targets outside the range, and adapting the search to rotated or monotonic data.

53

How can concurrent linear and binary searches safely share data?

Thread-safe sharing works by giving every search an immutable snapshot of the data. Writers replace the snapshot under a lock, while readers capture the current snapshot and search it without holding a data lock.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Safe Sharing Strategies

  • Immutable snapshot: Store the data as an immutable tuple. A search keeps a reference to that tuple, so a concurrent replacement cannot change the values being searched.

  • Copy-on-write: Build and validate the new tuple outside the lock, then assign it under the lock. For an externally mutable source, produce the incoming tuple while holding that source’s synchronization lock.

  • Read-write locking: If searches must always observe the newest data, readers can hold a shared/read lock during the search and writers take the exclusive/write lock. A single mutex also works, but it serializes readers.

  • Partitioned linear search: Divide the data into disjoint ranges and select the smallest matching global index. Use this only when true parallel execution is worthwhile.

  • Concurrent binary searches: Each search can independently use the same immutable snapshot. The algorithm itself does not need to be modified.

Variants and Complexity

Operation Best Average Worst Requirement
Sequential linear search O(1) O(n) O(n) Works on unsorted data
Binary search O(1) O(log n) O(log n) Sorted data
Lower bound O(log n) O(log n) O(log n) First index with value >= target
Upper bound O(log n) O(log n) O(log n) First index with value > target
First/last occurrence O(log n) O(log n) O(log n) Lower bound if equal; upper bound minus one
Rotated sorted search O(1) O(log n) O(log n) unique, O(n) with duplicates Determine which half is sorted
Binary search on an answer O(log R) O(log R) O(log R) R is the answer range; predicate must be monotonic

A partitioned linear search with p workers performs O(n) total CPU work and has ideal scan wall time O(ceil(n/p)), assuming enough processors and excluding coordination overhead. Its auxiliary space is O(p) for tasks and results. Binary search uses O(1) auxiliary space, including its O(1) recursion stack. Snapshot storage uses O(n) space and is not counted as per-search auxiliary space; the source input itself is also excluded from that per-search count.

Small Example

For [-2, 3, 3, 3, 8, 10] and target 3:

  1. Two linear-search workers find indices 1 and 3.

  2. Selecting the smallest match returns 1.

  3. Exact binary search examines the middle and returns 2.

  4. Lower bound returns 1; upper bound returns 4, so the last occurrence is 3.

Code Example

from bisect import bisect_left, bisect_right
from collections.abc import Iterable
from concurrent.futures import ThreadPoolExecutor
from threading import Lock


class ConcurrentSearcher:
    """Thread-safe searches over replaceable sorted integer snapshots."""

    def __init__(self, values: Iterable[int], max_workers: int = 4) -> None:
        if max_workers < 1:
            raise ValueError("max_workers must be positive")

        self._lock = Lock()
        self._max_workers = max_workers
        self._values = self._make_sorted(values)

    @staticmethod
    def _make_sorted(values: Iterable[int]) -> tuple[int, ...]:
        snapshot = tuple(values)
        if any(
            snapshot[index] > snapshot[index + 1]
            for index in range(len(snapshot) - 1)
        ):
            raise ValueError("values must be sorted in ascending order")
        return snapshot

    def replace(self, values: Iterable[int]) -> None:
        """Atomically replace the shared snapshot."""
        new_values = self._make_sorted(values)
        with self._lock:
            self._values = new_values

    def _snapshot(self) -> tuple[int, ...]:
        with self._lock:
            return self._values

    def linear_search(self, target: int) -> int | None:
        """Find the first target index using disjoint worker ranges."""
        values = self._snapshot()
        size = len(values)
        if size == 0:
            return None
        if values[0] == target:
            return 0

        worker_count = min(self._max_workers, size)
        chunk_size = (size + worker_count - 1) // worker_count

        def scan(chunk_index: int) -> int | None:
            start = chunk_index * chunk_size
            end = min(start + chunk_size, size)
            for index in range(start, end):
                if values[index] == target:
                    return index
            return None

        with ThreadPoolExecutor(max_workers=worker_count) as executor:
            matches = [
                index
                for index in executor.map(scan, range(worker_count))
                if index is not None
            ]

        return min(matches) if matches else None

    @staticmethod
    def _binary_search(
        values: tuple[int, ...], target: int
    ) -> int | None:
        lo, hi = 0, len(values) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if values[mid] < target:
                lo = mid + 1
            elif values[mid] > target:
                hi = mid - 1
            else:
                return mid
        return None

    def binary_search(self, target: int) -> int | None:
        """Find any target using the inclusive interval [lo, hi]."""
        return self._binary_search(self._snapshot(), target)

    def lower_bound(self, target: int) -> int:
        """Return the first index whose value is at least target."""
        return bisect_left(self._snapshot(), target)

    def upper_bound(self, target: int) -> int:
        """Return the first index whose value is greater than target."""
        return bisect_right(self._snapshot(), target)

    def first_occurrence(self, target: int) -> int | None:
        """Return the first target index, if present."""
        values = self._snapshot()
        position = bisect_left(values, target)
        if position < len(values) and values[position] == target:
            return position
        return None

    def last_occurrence(self, target: int) -> int | None:
        """Return the last target index, if present."""
        values = self._snapshot()
        position = bisect_right(values, target) - 1
        if position >= 0 and values[position] == target:
            return position
        return None

    def binary_search_many(self, targets: Iterable[int]) -> list[int | None]:
        """Search all targets against one consistent snapshot."""
        values = self._snapshot()
        target_list = list(targets)
        if not target_list:
            return []

        def search(target: int) -> int | None:
            return self._binary_search(values, target)

        with ThreadPoolExecutor(
            max_workers=min(self._max_workers, len(target_list))
        ) as executor:
            return list(executor.map(search, target_list))


searcher = ConcurrentSearcher([-2, 3, 3, 3, 8, 10], max_workers=2)
print(searcher.linear_search(3))                 # 1
print(searcher.binary_search(3))                 # 2
print(searcher.first_occurrence(3))              # 1
print(searcher.last_occurrence(3))               # 3
print(searcher.binary_search_many([3, 8, 99]))   # [2, 4, None]

Common Pitfalls

  • Letting writers modify the collection while a binary search is running can invalidate its ordering invariant.

  • Locking only the search while writers remain unlocked does not make the data safe.

  • Partitioned searches must return the smallest matching global index when first-occurrence semantics are required.

  • mid = lo + (hi - lo) // 2 avoids fixed-width overflow from lo + hi; the interval here is inclusive [lo, hi].

  • CPython’s GIL can prevent CPU speedup from pure-Python threads; processes or native implementations are needed for true parallel CPU execution.

  • The implementation handles empty and singleton inputs, duplicates, negative values, absent targets, and already sorted data. It rejects unsorted snapshots because binary search requires ordering.

54

How do search algorithms optimize machine learning models?

Search algorithms support model optimization by systematically exploring candidate configurations, such as hyperparameters, model architectures, preprocessing choices, and decision thresholds. The search evaluates each candidate using a validation metric and selects the configuration that performs best under the chosen constraints.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Search Algorithms Are Used

A typical machine-learning workflow separates two optimization layers:

  • Inner optimization: Gradient descent, Adam, and similar algorithms adjust model parameters during training.

  • Outer search: A search algorithm selects configurations such as learning rate, regularization strength, tree depth, number of estimators, or feature subsets.

Common outer searches include:

  • Grid search: Exhaustively evaluates every point in a predefined parameter grid.

  • Random search: Samples configurations from specified distributions and can find good candidates with fewer evaluations when only a few parameters strongly affect performance.

  • Bayesian optimization: Uses previous evaluations to select promising configurations; it is effective for expensive black-box objectives but is more complicated to implement and maintain.

  • Evolutionary search: Maintains a population and generates candidates through mutation and combination.

  • Linear or binary search: Applies to candidate lookup when the candidates are sorted or the objective has a suitable monotonic structure.

Training data is used for model fitting, while validation or cross-validation results guide the search. A final test set should remain untouched until model selection is complete.

Search Variants

  • Linear search checks elements sequentially, works with unsorted data, and takes O(n) time.

  • Binary search requires sorted data or a monotonic predicate and takes O(log n) time. The implementation below uses the inclusive interval [lo, hi] and computes mid = lo + (hi - lo) // 2; this midpoint formula avoids overflow from lo + hi in fixed-width languages.

  • First and last occurrence: bisect.bisect_left finds the first position whose value is at least the target, while bisect.bisect_right finds the position after equal values. Their difference identifies the duplicate range.

  • Rotated sorted array: A modified binary search identifies a sorted half and discards the half that cannot contain the target. It takes O(log n) time for distinct elements; duplicates can require a linear fallback.

  • Binary search on the answer: Searches an integer range using a monotone feasibility predicate, taking O(log R) predicate evaluations for range size R. Most hyperparameter relationships are not monotone, so this assumption must be established first.

Complexity

Let n be the number of searched elements, p the number of parameters, S the total number of supplied parameter values, G the number of grid combinations, k the number of random trials, and C the maximum cost of one model evaluation. Input data is excluded from auxiliary space.

Approach Time Auxiliary space Best, average, and worst case
Linear search O(n) O(1) Same in all cases
Binary search O(log n) O(1) Same in all cases
Grid search O(G × (p + C)) O(S + p) for the shown itertools.product implementation Same in all cases
Random search O(k × (p + C)) O(p) when retaining only the best candidate Same asymptotic evaluation count in all cases
Evolutionary search O(r × P × (C + p)) O(P × p) Same for fixed generations; early stopping can reduce the best case
Bayesian optimization O(k × (C + B(k) + A(k))) Model-dependent; commonly O(k² + kp) for an exact Gaussian process Average and worst costs depend on the surrogate and acquisition optimizer

Here r is the number of generations, P the population size, B(k) the surrogate-fitting cost, and A(k) the acquisition-optimization cost. These lookup complexities count comparisons; when every candidate requires model training, include the evaluation cost C. Amortized analysis is not normally needed for the outer search, although individual model-fitting algorithms may have amortized costs.

Walkthrough

Step Learning rate Maximum depth Objective
1 0.01 2 -0.11
2 0.01 4 -0.13
3 0.10 2 -0.02
4 0.10 4 -0.04

The grid search evaluates all four candidates and selects candidate 3 because it has the highest objective value, -0.02.

Code Example

from bisect import bisect_left, bisect_right
from collections.abc import Callable, Mapping, Sequence
from itertools import product


def grid_search(
    parameter_grid: Mapping[str, Sequence[float]],
    objective: Callable[[Mapping[str, float]], float],
) -> tuple[dict[str, float], float]:
    """Return the best parameter combination and its objective value."""
    if not parameter_grid or any(len(values) == 0 for values in parameter_grid.values()):
        raise ValueError("The parameter grid must contain parameters and values.")

    best_params: dict[str, float] = {}
    best_score = float("-inf")

    for values in product(*parameter_grid.values()):
        candidate = dict(zip(parameter_grid.keys(), values, strict=True))
        score = objective(candidate)

        if score > best_score:
            best_score = score
            best_params = candidate

    return best_params, best_score


def binary_search(values: Sequence[int], target: int) -> int:
    """Return an index of target in sorted values, or -1 if absent."""
    lo = 0
    hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1


def occurrence_bounds(values: Sequence[int], target: int) -> tuple[int, int]:
    """Return the first and last occurrence indexes of target, or (-1, -1)."""
    first = bisect_left(values, target)
    if first == len(values) or values[first] != target:
        return -1, -1
    return first, bisect_right(values, target) - 1


def objective(params: Mapping[str, float]) -> float:
    """Stand in for a validation metric; higher values are preferred."""
    return -abs(params["learning_rate"] - 0.1) - 0.01 * params["max_depth"]


best_params, best_score = grid_search(
    {"learning_rate": [0.01, 0.1], "max_depth": [2, 4]},
    objective,
)
print(best_params, best_score)
# Expected output: {'learning_rate': 0.1, 'max_depth': 2} -0.02

print(binary_search([-4, 0, 0, 3, 8], 0))
# Expected output: 1

print(occurrence_bounds([-4, 0, 0, 3, 8], 0))
# Expected output: (1, 2)

Common Pitfalls

  • Data leakage: Do not select hyperparameters using the test set.

  • Validation overfitting: Repeated searches can overfit validation data; retain a final untouched test set.

  • Stochasticity: Fix seeds or repeat evaluations when comparing candidates.

  • Unbounded spaces: Constrain random and Bayesian searches to practical, valid configurations.

  • Incorrect monotonic assumptions: Binary search is unsafe when the predicate is not monotone.

  • Off-by-one errors: State whether bounds are inclusive or exclusive and test the empty and one-element cases.

  • Input mutation: If sorting is required, sort a copy when the caller’s ordering must be preserved.

  • Edge cases: grid_search rejects an empty grid or empty value sequence and handles one-element grids, duplicates, negative values, and unordered parameter sequences. The binary functions handle empty, one-element, negative, and already sorted inputs; binary_search returns any duplicate match, while occurrence_bounds returns the first and last.

  • Interview follow-up: Explain why random search can outperform grid search when many parameters have little effect on performance.

55

How do search algorithms support network routing and optimization?

Search algorithms help networks choose routes, minimize cost, and find feasible configurations by systematically exploring candidates. In routing, the network is usually modeled as a graph whose vertices are routers or links and whose edge weights represent latency, bandwidth, monetary cost, or another metric.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

Search algorithms solve different kinds of problems:

  • Linear search examines candidates one by one. It works on sorted or unsorted data and is appropriate for small candidate sets.

  • Binary search repeatedly eliminates half of a sorted interval. It also applies when a condition is monotonic, even if the underlying data is not explicitly sorted.

  • BFS finds paths with the fewest edges, making it suitable for hop-count routing where every edge has equal cost.

  • Dijkstra’s algorithm finds minimum-cost paths when edge weights are non-negative. Link-state routing protocols such as OSPF use a Dijkstra-style shortest-path calculation.

  • Binary search on the answer finds an optimal threshold when feasibility is monotonic—for example, the minimum bandwidth required for a flow to succeed.

Choosing a Search Strategy

Space figures below are auxiliary space and exclude the input; the corresponding total space including the input is also stated.

Approach Time: Best / Average / Worst Auxiliary Space Total Space Including Input When to Use
Linear search O(1) / O(n) / O(n) O(1) O(n) Small or unsorted candidate lists
Binary search O(1) / O(log n) / O(log n) O(1) iteratively O(n) Sorted data or a monotonic condition
BFS O(V+E) / O(V+E) / O(V+E) O(V) O(V+E) Unweighted graphs or minimum-hop paths
Dijkstra O((V+E) log V) / O((V+E) log V) / O((V+E) log V) O(V+E) with a lazy heap O(V+E) Non-negative weighted routing costs

The reasons are straightforward:

  • Linear search may find the first item immediately but may inspect all n items.

  • Binary search halves the remaining interval, requiring O(log n) comparisons.

  • BFS processes each vertex and edge at most once.

  • Dijkstra’s priority queue performs logarithmic heap operations while processing V vertices and E edges.

No recursive calls are used, so the recursion stack is O(1). For binary search on a numeric answer with range size R, where each feasibility check costs C, total time is O(log R × C).

Routing and Optimization Example

Consider the graph:

  • A → B: cost 1

  • A → C: cost 4

  • B → C: cost 2

  • C → D: cost 3

Dijkstra’s algorithm processes states as follows:

Popped Vertex Tentative Distances
A A=0, B=1, C=4
B A=0, B=1, C=3
C A=0, B=1, C=3, D=6
D A=0, B=1, C=3, D=6

The final route to D is A → B → C → D, with cost 6.

In a real network, these weights might represent propagation delay, congestion, or an administrative routing cost. Optimization can then impose additional checks, such as minimum bandwidth, maximum latency, or policy constraints.

Common Pitfalls

  • Binary search requires sorted data or a monotonic predicate: Otherwise, discarded candidates may contain the answer.

  • Negative weights invalidate Dijkstra’s algorithm: Use an algorithm that supports negative edges, such as Bellman–Ford.

  • Disconnected graphs: Unreachable vertices are absent from the returned distance map.

  • Cycles require tracking processed vertices: The settled set prevents repeated processing.

  • Off-by-one errors: Define whether an interval is inclusive [lo, hi] or half-open [lo, hi).

  • Integer overflow in Java or C++: Calculate mid as lo + (hi - lo) // 2 rather than (lo + hi) // 2.

  • Input mutation: Avoid modifying the original graph or candidate list unless the API explicitly permits it.

Common interview follow-ups include choosing between BFS and Dijkstra, handling negative edge costs, proving correctness, and identifying when binary search on the answer is valid.

56

How does branch and bound improve search algorithm efficiency?

Branch and bound improves search efficiency by maintaining the best complete solution found so far and pruning partial solutions that cannot improve it. When its bounds are valid, it preserves exactness while often examining far fewer states than blind exhaustive search.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Branch and bound combines three ideas:

  • Branching: Split the remaining possibilities into alternatives, such as including or excluding an item or choosing one of several cities.

  • Bounding: Estimate the best result obtainable from each partial solution.

  • Pruning: Discard a branch when its bound shows that it cannot improve the current incumbent.

For a maximization problem, the bound must be an upper bound. For a minimization problem, it must be a lower bound. An invalid bound can prune an optimal solution, so the implementation must never underestimate a possible maximization result or overestimate a possible minimization result.

This technique is commonly used for combinatorial optimization problems such as 0/1 knapsack, traveling-salesperson routing, scheduling, and integer programming.

Search Procedure

A typical branch-and-bound search follows these steps:

  1. Establish a feasible incumbent, meaning the best complete solution currently known.

  2. Select an unexplored partial solution and generate its possible successors.

  3. Calculate a valid, preferably tight, bound for each successor.

  4. Prune any successor whose bound cannot beat the incumbent.

  5. Continue exploring the remaining branches until none are left.

  6. Update the incumbent whenever a better feasible complete solution is found.

The incumbent need not be optimal initially; it should simply be valid and reasonably strong. A good incumbent helps pruning begin earlier, while a tight bound reduces the number of surviving branches.

Efficiency and Complexity

If each search state has branching factor b and the search depth is d, the worst-case number of explored states is O(b^d) for b > 1. This remains exponential in the depth even though pruning may reduce the explored portion substantially.

  • Best time: Problem-dependent; O(1) is possible when a strong incumbent is already available and the root bound immediately prunes the search. Otherwise, some work is required to obtain or evaluate an incumbent.

  • Average time: Instance-dependent; there is no standard tighter asymptotic bound without assumptions about the data and bound quality.

  • Worst time: O(b^d) when bound evaluation takes O(1); more generally, it is O(V × c), where V is the number of visited states and c is the cost of evaluating a bound.

  • Auxiliary space: O(d) for a depth-first recursion stack or explicit stack, plus any bound tables. If bounds are computed on demand, the bound itself need not require additional storage. The input is not counted.

Search method Time Auxiliary space Requirement
Linear search O(n) O(1) No ordering requirement
Binary search O(log n) O(1) Sorted data or a suitable monotonic condition
Branch and bound O(b^d) worst case Typically O(d) plus bound data Valid optimistic bounds and a feasible incumbent

Unlike linear or binary search, branch and bound is intended for structured combinatorial spaces where good estimates can eliminate entire groups of alternatives.

Example: 0/1 Knapsack

Consider items with weights [2, 3, 4], values [3, 4, 5], and capacity 5. A valid upper bound is the current value plus the values of all remaining items, ignoring the capacity constraint.

  1. At the root, the current value is 0, so the upper bound is 3 + 4 + 5 = 12.

  2. Including the item with weight 2 and value 3 produces weight 2 and value 3.

  3. Including the item with weight 3 and value 4 then produces weight 5 and value 7.

  4. The remaining item has weight 4, so it cannot be included.

  5. The complete feasible solution has value 7, which becomes the incumbent.

  6. Backtracking explores the remaining alternatives, but none can produce a feasible value greater than 7.

The bound in this example is intentionally simple and somewhat loose. Capacity-aware bounds generally prune more aggressively.

Common Pitfalls

  • Invalid bound: A bound in the wrong direction can silently discard the optimal solution.

  • Weak bound or poor incumbent: Either causes unnecessary exploration; tighten the bound and find a good feasible solution early.

  • Equality handling: Pruning on equality is valid only when objective ties do not matter. Preserve ties when secondary criteria or all optimal solutions are required.

  • Off-by-one errors: Check index ranges and ensure bounds include or exclude boundary items intentionally.

  • Integer overflow: Bound calculations can overflow fixed-width integers in languages such as Java or C++.

  • Mutating input: Copy data before sorting or reordering it unless mutation is intentional.

  • Cycles in graph searches: Track visited states or restrict the search to a DAG to avoid repeated exploration.

  • Typical follow-up: Interviewers commonly ask how to construct a valid bound, why the method remains optimal, and how its runtime differs between easy and adversarial instances.

57

How can a self-organizing list optimize searches using access history?

A self-organizing list uses access history to reorder its elements so that future searches can be faster. A common policy is move-to-front: search linearly, then move the matched element to the front while preserving the relative order of the other elements. This favors recently accessed elements; frequency-aware policies are needed to favor frequently accessed elements explicitly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Scan the list from left to right.

  2. If the target is found, move that element to index 0.

  3. Return 0, its new position.

  4. If the target is absent, return None.

Move-to-front records recent access history directly in the list order. For example, after the first request for "gamma", every subsequent request for the same element requires only one comparison.

Complexity

For a list containing n elements:

  • Best case: O(1) time when the target is already first.

  • Average case: O(n) when requests are independent and uniformly distributed among the stored elements (about (n + 1) / 2 comparisons). Move-to-front only beats a static list when requests are skewed or show recency locality.

  • Worst case: O(n) time when the target is last or absent. Moving the match to the front also takes O(n) in the worst case.

  • Space: O(1) auxiliary space because the list is modified in place. The input itself is not counted, and there is no recursion stack.

Comparison With Other Searches

Approach Best Average Worst Auxiliary Space When to Use
Linear search O(1) O(n) O(n) O(1) Unsorted data
Binary search O(log n) O(log n) O(log n) O(1) Sorted data
Move-to-front list O(1) O(n) for uniform requests; lower for skewed or repeated requests O(n) O(1) Repeated accesses with recency locality

For sorted data, binary-search variants take O(log n) time and O(1) auxiliary space. These include finding the first or last occurrence, finding lower and upper bounds with bisect_left and bisect_right, and searching a rotated sorted array with distinct values. Rotated-array search with duplicates can degrade to O(n) worst-case time. Binary search on an answer range of size R takes O(log R) time when its feasibility condition is monotone.

Example Walkthrough

Starting state:

["alpha", "beta", "gamma"]
Request Comparisons State After Access
"gamma" 3 ["gamma", "alpha", "beta"]
"gamma" 1 ["gamma", "alpha", "beta"]

The second request becomes faster because the previous successful access moved "gamma" to the front.

Code Example

from typing import TypeVar

T = TypeVar("T")


def adaptive_search(values: list[T], target: T) -> int | None:
    """Find target and move the first matching element to the front."""
    for index, value in enumerate(values):
        if value == target:
            if index != 0:
                matched = values[index]
                for position in range(index, 0, -1):
                    values[position] = values[position - 1]
                values[0] = matched
            return 0

    return None


values = ["alpha", "beta", "gamma"]
result = adaptive_search(values, "gamma")

print(result)
print(values)

# Expected output:
# 0
# ['gamma', 'alpha', 'beta']

Common Pitfalls

  • Mutating input: The function reorders the caller’s list. Copy it first if its original order must be preserved.

  • Duplicates: The first matching element encountered is moved to the front, and the function returns 0.

  • Empty or one-element lists: An empty list returns None; a one-element list takes O(1) time.

  • Negative values: Negative numbers work because the algorithm uses equality rather than ordering.

  • Already sorted input: A successful search may make the list unsorted, preventing later binary search.

  • Unrealistic average-case assumptions: Move-to-front helps only when access is skewed or repeated; under uniform requests the average stays O(n), and the worst case is always O(n).

  • Index changes: Callers should not assume an index obtained before the search remains valid after the list is reorganized.

59

How can binary and linear search be combined for non-uniformly distributed data?

Hybrid search uses a fast selective search to narrow the candidate region, then a localized scan to finish the lookup. This combines the predictable performance of binary search with the simplicity of linear search and can be especially useful for sorted data with uneven value spacing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A common binary-linear hybrid divides a sorted collection into fixed-size blocks:

  1. Examine the last value of each block, which is its maximum because the collection is sorted.

  2. Use binary search over those block maxima to identify the first block that could contain the target.

  3. Scan that block linearly.

For example, with [0, 1, 2, 10, 100, 1000] and a block size of 2:

  • The blocks are [0, 1], [2, 10], and [100, 1000].

  • Binary search over block maxima 1, 10, and 1000 selects the third block.

  • A linear scan finds 100 at index 4.

The uneven spacing between values does not affect the algorithm’s correctness or worst-case bound.

Complexity Comparison

Approach Best Average Worst Auxiliary space
Linear search O(1) O(n) O(n) O(1)
Binary search O(1) O(log n) O(log n) O(1)
Binary block search + linear scan O(log(n/B)) O(log(n/B) + B) O(log(n/B) + B) O(1)
Bounded interpolation search + binary fallback O(1) Distribution-dependent; O(log log n) for a matching distribution O(k + log n) O(1)
  • B is the number of elements in one block.

  • k is the maximum number of allowed interpolation probes.

  • With fixed k, the bounded hybrid has an O(log n) worst case.

  • All implementations are iterative, so the recursion stack uses O(1) space.

  • Auxiliary space excludes the input collection. Counting the input itself, storage is O(n).

Strategies for Non-Uniform Data

  • Block-based hybrid: Use a moderate block size such as 16 or 32. A smaller block makes scanning faster but increases the number of binary-search steps; a larger block has the opposite trade-off.

  • Bounded interpolation search: Estimate an index from the target’s value, then fall back to binary search after a fixed number of unsuccessful probes. Interpolation search alone has an O(n) worst case because a skewed distribution can repeatedly select poor positions.

  • Quantile buckets: If many searches are performed against a stable dataset, precompute buckets containing similar numbers of elements. Binary-search the buckets and scan the selected bucket. With m buckets of at most B elements, this costs O(log m + B) per search and O(m) additional index space.

  • Direct lookup for repeated queries: If the same values are queried frequently, build a value-to-index dictionary for O(1) average lookup, accepting O(n) additional space.

  • Unsorted data: Sorting costs O(n log n) time and O(n) or O(log n) auxiliary space depending on the algorithm. For only one or a few lookups, linear search may be cheaper than sorting first.

Related Binary-Search Variants

Variant Standard approach
First or last occurrence Use bisect_left(values, target) or bisect_right(values, target) - 1
Lower and upper bounds Use bisect_left and bisect_right on sorted values
Rotated sorted array Locate the rotation, then binary-search the appropriate sorted segment
Binary search on an answer Binary-search a numeric range using a monotonic feasibility predicate

The boundary variants take O(log n) time and O(1) auxiliary space. Interpolation is generally not suitable for rotated arrays; for binary search on an answer, it requires a safe monotonic numeric function.

Code Example

from collections.abc import Sequence


def hybrid_block_search(
    values: Sequence[int], target: int, block_size: int = 32
) -> int:
    """Find target in ascending sorted values using block binary and linear search."""
    if block_size <= 0:
        raise ValueError("block_size must be positive")
    if not values:
        return -1

    block_count = (len(values) + block_size - 1) // block_size
    low, high = 0, block_count - 1

    # Find the first block whose maximum is at least the target.
    while low <= high:
        mid = low + (high - low) // 2
        block_end = min((mid + 1) * block_size, len(values))

        if values[block_end - 1] < target:
            low = mid + 1
        else:
            high = mid - 1

    if low >= block_count:
        return -1

    # Search only the selected block.
    start = low * block_size
    end = min(start + block_size, len(values))

    for index in range(start, end):
        if values[index] == target:
            return index
        if values[index] > target:
            return -1

    return -1


values = [0, 1, 2, 10, 100, 1000]
print(hybrid_block_search(values, 100, block_size=2))  # 4

Common Pitfalls

  • Unsorted input: Binary, interpolation, and block searches require ascending order.

  • Incorrect interval bounds: Use consistent inclusive or exclusive bounds; this implementation uses inclusive low and high.

  • Duplicate values: The block hybrid returns an occurrence but does not guarantee the first or last one; use bisect_left or bisect_right for that requirement.

  • Edge cases: Empty input returns -1; a one-element collection works; negative values are supported; already sorted input is assumed.

  • Poor tuning: A very large block weakens the linear-search component, while a very small block increases binary-search overhead.

  • Overflow in other languages: Calculate mid as low + (high - low) // 2 to avoid integer overflow.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 59 Searching Algorithms answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects