Searching & Array Techniques

Linear search: the baseline

Looking for your keys, you check every pocket one by one. That is linear search: examine each item until you find the target or run out. It needs no preparation and works on any iterable, sorted or not.

def linear_search(items: list[int], target: int) -> int:
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

Invariant: before checking index i, the target is not in items[:i]. Cost: best O(1) (first item), worst and average O(n), O(1) space. Python's x in list, list.index, and list.count are linear searches written in C. For one-off searches on small or unsorted data, linear search is the right answer: sorting first would cost O(n log n).

Remember: linear search is O(n) and needs nothing; anything faster needs structure: order (binary search) or hashing (sets and dicts).

Binary search in depth

Intuition: guessing a number between 1 and 100 when told "higher" or "lower." The smart first guess is 50, which eliminates half the possibilities. Then 25 or 75. Each guess halves the range, so 7 guesses always suffice (2⁷ = 128 ≥ 100). Looking up a word in a paper dictionary works the same way. The requirement is that the data is sorted, so one comparison tells you which half to discard.

Write it from an invariant

Most binary-search bugs come from fuzzy thinking about what lo and hi mean. Pick a meaning, write it down as an invariant, and every line follows. We use the half-open interval convention [lo, hi), matching Python's range and slices:

lo, hi = 0, n                    # the whole list is still possible
while lo < hi:                   # the interval [lo, hi) is non-empty
    mid = (lo + hi) // 2         # lo <= mid < hi
    if a[mid] < target: lo = mid + 1     # target is right of mid
    elif a[mid] > target: hi = mid       # target is left of mid (hi is exclusive)
    else: return mid
return -1                         # interval empty: not present

Termination: every iteration shrinks hi - lo because lo <= mid < hi, so mid + 1 > lo and mid < hi. Complexity: O(log n) time (each step halves the interval: a billion items need at most 30 steps), O(1) space. Best case O(1).

The off-by-one traps

Lower bound and upper bound

"Is it there?" is less useful than "where would it go?" The lower bound is the first index whose item is >= target; the upper bound is the first index whose item is > target. Equal items occupy exactly a[lower:upper], so upper - lower counts occurrences, and both indexes are where you would insert to keep the list sorted.

def lower_bound(a: list[int], target: int) -> int:
    lo, hi = 0, len(a)            # invariant: a[:lo] < target <= a[hi:]
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo                     # lo == hi: the boundary

This form never "finds" anything mid-loop; it just narrows down to the boundary between "too small" and "big enough." That is the most important idea in this module: binary search finds the boundary of a monotone predicate. Here the predicate is a[i] >= target: false, false, ..., false, true, ..., true. Change < to <= and you get the upper bound.

Remember: choose half-open [lo, hi), write the invariant, use lo = mid + 1 / hi = mid, and think "boundary of a true/false predicate."

The bisect module

The standard library ships tested, C-accelerated binary search. You should use it instead of hand-writing the loop in production code.

The key= argument (Python 3.10+)

All bisect functions accept key=. It is applied to the list items, not to the value you search for, so pass the already-extracted key as x. For insort, the key is applied to the new item too, so pass the whole record.

Remember: bisect_left is lower bound, bisect_right is upper bound; key= applies to list items only (and to the inserted item in insort).

Binary search on the answer

Binary search works on any monotone yes/no question over a range of numbers, not just on arrays. If "can we do it with capacity c?" is false for small c and true for every c past some threshold, the smallest feasible c is a boundary, and you can find it in O(log range) feasibility checks.

Minimum ship capacity

Packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] must ship in order within 5 days. Each day the ship carries consecutive packages up to its capacity. What is the smallest capacity that works? A capacity below the heaviest package can never work; the total weight always works. In between, more capacity never hurts: monotone.

lo = max(weights); hi = sum(weights)      # answer is in [lo, hi]
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid): hi = mid           # mid works; maybe smaller works too
    else:             lo = mid + 1       # mid fails; need more
return lo

Integer square root

The predicate "m * m <= n" is true then false as m grows, so the largest m where it holds is ⌊√n⌋. This works for integers far too big for floating point, where int(n ** 0.5) is wrong.

Complexity: O(log(hi − lo)) checks times the cost of one check. For shipping that is O(n log(sum)). When to use: "find the minimum X such that ..." or "maximum X such that ..." where checking a given X is easy and feasibility is monotone in X.

Two pointers

Intuition: two people walk toward each other from opposite ends of a sorted bookshelf, looking for two books whose prices add up to a gift card's value. If the pair is too expensive, the person on the right steps left (cheaper); too cheap, the person on the left steps right. Each step rules out a whole row of pairs, so the walk takes O(n) instead of checking all O(n²) pairs.

Invariant: no valid pair uses an index outside [i, j]. The comments explain why each move preserves it. Cost: O(n) time, O(1) space (after an O(n log n) sort, if needed).

Same-direction pointers: dedupe in place

A slow pointer marks where the next kept item goes; a fast pointer scans. This is how you compact a sorted array without extra memory.

Three-sum

Find all unique triples summing to zero. Sort, fix the first element, then run the two-pointer pair search on the rest. O(n²) instead of O(n³), with duplicates skipped by stepping past equal values.

def three_sum(nums: list[int]) -> list[tuple[int, int, int]]:
    nums = sorted(nums)
    out = []
    for k in range(len(nums) - 2):
        if k and nums[k] == nums[k - 1]:
            continue                       # same first element: same triples
        i, j = k + 1, len(nums) - 1
        while i < j:
            s = nums[k] + nums[i] + nums[j]
            if s < 0:
                i += 1
            elif s > 0:
                j -= 1
            else:
                out.append((nums[k], nums[i], nums[j]))
                i += 1
                while i < j and nums[i] == nums[i - 1]:
                    i += 1
    return out

Remember: opposite-end pointers on sorted data exploit order to discard many pairs per step; slow/fast pointers compact or partition in place.

Sliding windows

Intuition: a train window shows a fixed stretch of countryside; as the train moves, one tree enters on the right and one leaves on the left. You do not re-look at the whole view, you just update for what entered and what left. A sliding window keeps a running summary of a contiguous subarray and updates it in O(1) per step.

Fixed-size window

Maximum sum of any k consecutive items: compute the first window's sum, then slide: add the entering item, subtract the leaving one. O(n) instead of O(n·k).

Variable-size window

For "longest/shortest subarray such that ...", grow the window by moving right; whenever the window breaks the rule, shrink it by moving left until it is valid again. Each index enters once and leaves once, so the total work is O(n) even though there is a loop inside a loop.

Invariant: s[left:right + 1] has no repeated characters, and no valid window ending at right starts before left. When to use: contiguous subarrays or substrings where a window that is valid stays valid when shrunk (or when grown). It does not work for sums with negative numbers, where shrinking can make a sum bigger; use prefix sums there.

Remember: fixed windows add one and drop one; variable windows expand right and shrink left; each index moves forward at most once per pointer.

Prefix sums and difference arrays

Intuition: a car's odometer. To know how far you drove between Tuesday and Friday, you do not add up every trip; you subtract Tuesday's odometer reading from Friday's. A prefix sum array stores the running total, P[i] = a[0] + ... + a[i-1] with P[0] = 0, and then any range sum is one subtraction: sum(a[i:j]) == P[j] - P[i].

Difference arrays: the reverse trick

Suppose you must apply many range updates ("add 5 to every seat from row 10 to 40") and read the final array once. A difference array D records only the changes at the boundaries: add v at D[i] and subtract v at D[j]. Taking the prefix sum of D at the end reconstructs every value. Each update is O(1); the final pass is O(n).

Complexity: prefix sums O(n) build, O(1) per query, O(n) space. Difference arrays O(1) per update, O(n) to materialize. If you need updates and queries interleaved, a Fenwick tree (M27) does both in O(log n). Two-dimensional prefix sums work the same way for rectangle sums in images and grids.

Remember: prefix sums turn range queries into subtraction; difference arrays turn range updates into two point updates; they are inverses of each other.

Hashing versus sorting

Many search problems can be solved two ways. "Does any pair sum to t?" can sort then use two pointers (O(n log n), O(1) extra space), or scan once with a set of seen values (O(n) expected, O(n) space).

def has_pair_hash(nums: list[int], t: int) -> bool:
    seen: set[int] = set()
    for x in nums:
        if t - x in seen:
            return True
        seen.add(x)
    return False

def has_pair_sort(nums: list[int], t: int) -> bool:
    a = sorted(nums)
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == t:
            return True
        i, j = (i + 1, j) if s < t else (i, j - 1)
    return False

Remember: hash for exact lookups, sort for order-dependent questions; when both work, measure.

Practice

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

from bisect import bisect_left, bisect_right

def find_range(a, x):
    lo = bisect_left(a, x)
    if lo == len(a) or a[lo] != x:
        return (-1, -1)
    return (lo, bisect_right(a, x) - 1)

def min_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        needed = sum((p + mid - 1) // mid for p in piles)
        if needed <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

def three_sum(nums):
    nums = sorted(nums)
    out = []
    for k in range(len(nums) - 2):
        if k and nums[k] == nums[k - 1]:
            continue
        i, j = k + 1, len(nums) - 1
        while i < j:
            s = nums[k] + nums[i] + nums[j]
            if s < 0:
                i += 1
            elif s > 0:
                j -= 1
            else:
                out.append((nums[k], nums[i], nums[j]))
                i += 1
                while i < j and nums[i] == nums[i - 1]:
                    i += 1
    return out

def min_window_len(nums, target):
    best = 0
    left = 0
    total = 0
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            length = right - left + 1
            if best == 0 or length < best:
                best = length
            total -= nums[left]
            left += 1
    return best

from itertools import accumulate

def apply_updates(n, updates):
    diff = [0] * (n + 1)
    for start, stop, value in updates:
        diff[start] += value
        diff[stop] -= value
    return list(accumulate(diff[:n]))

def prefix_sums(a):
    return [0, *accumulate(a)]

Mini-project: "find my range" log search

pixi init logrange && cd logrange
pixi add pytest
pixi run python make_log.py app.log --lines 500000
pixi run python logrange.py app.log --start 2026-10-14T14:02:00 --end 2026-10-14T14:07:00

from bisect import bisect_left
from datetime import datetime

def parse_ts(line: str) -> datetime:
    return datetime.fromisoformat(line.split(" ", 1)[0])

def find_range(lines: list[str], start: datetime, end: datetime) -> list[str]:
    """Return lines with start <= timestamp < end."""
    lo = bisect_left(lines, start, key=parse_ts)
    hi = bisect_left(lines, end, key=parse_ts)
    return lines[lo:hi]

Quiz

Recap

• Linear search is O(n) and needs no structure; binary search is O(log n) and needs order.
• Write binary search from an invariant on a half-open interval; it finds the boundary of a monotone predicate.
• bisect_left/bisect_right are lower/upper bound; key= applies to list items.
• Binary search on the answer solves "smallest X that works" when feasibility is monotone.
• Two pointers exploit order to discard many candidates per step; slow/fast pointers compact in place.
• Sliding windows update a running summary in O(1) per step; variable windows expand right and shrink left.
• Prefix sums give O(1) range sums; difference arrays give O(1) range updates.
• Hash for exact lookups and counting; sort for ranges, nearest values, and low memory.

Going further

• bisect: array bisection algorithm in the Python docs
• itertools.accumulate
• Jon Bentley, Programming Pearls, column 4, on writing correct binary search
• Next: M31 Graph Algorithms searches through networks instead of arrays.