Skip to content

Searching#

Searching means locating a target value (or its position) inside a collection. The right algorithm depends on whether the data is sorted and whether you need one answer or all occurrences.

Comparison#

Algorithm Preconditions Time Space When to use
Linear search None O(n) O(1) Unsorted data; small n; single scan
Binary search Sorted array O(log n) O(1) iterative Sorted data; large n; find exact value or boundary

Scan every element until you find the target or exhaust the array.

def linear_search(arr: list, target) -> int:
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

Time: O(n) worst and average — each element checked once.
Space: O(1) — only an index variable.

When to use:

  • The array is not sorted (sorting first costs O(n log n), often not worth it for one query).
  • You need the first occurrence in original order.
  • The list is small (constant size); simplicity beats log factors.

Limitations: Repeated searches on the same unsorted array are expensive; consider sorting once + binary search, or building a hash map for O(1) lookups.

Requires a sorted array (or a monotonic predicate — “first index where condition becomes true”). Compare against the middle element and discard half the search space each step.

def binary_search(arr: list, target) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Time: O(log n) — halve the interval each iteration; at most ⌊log₂ n⌋ + 1 comparisons.
Space: O(1) iterative; O(log n) if implemented recursively (call stack).

When to use:

  • Data is already sorted or sorting cost is amortized over many queries.
  • You need O(log n) lookup in a static array.
  • The problem reduces to “find the boundary” (first ≥ x, last ≤ x) on a monotonic sequence — the same template applies with adjusted equality checks.

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

Equivalent to (left + right) // 2 but safe when indices are large (relevant in C++/Java; good habit in Python too).

Iterative vs recursive#

Style Space Notes
Iterative O(1) Preferred in interviews
Recursive O(log n) stack Mirrors the mathematical definition

Linear vs binary — decision guide#

Choosing linear search vs binary search

Common misconceptions#

  1. Binary search on unsorted data — incorrect; you must sort first (O(n log n)) or use linear / hashing.
  2. Binary search only finds exact matches — the same loop finds lower bound, upper bound, and insertion point by changing the update rule and return value.
  3. Linear search is always bad — for tiny arrays or one-off scans, the constant overhead of binary search may not matter.