Search Variants, Galloping Search & Range Queries

The gap this subtopic closes

The first two subtopics cover the two shapes you'll actually be asked to code: exact/boundary search on a real array, and binary search over an abstract answer space. This subtopic is about everything around those two skills that separates "I memorized the binary search template" from "I understand what binary search fundamentally requires and when something else is a better tool." It covers what to do when you don't know the array's length, when a full binary-search-capable data structure is overkill, why binary search's O(log n) is a hard floor rather than a starting point, and two real, named production techniques (git bisect, and finding the end of an append-only log) that are binary search wearing a disguise.

When linear search is still the right answer

Before reaching for anything clever: binary search requires random access to a sorted (or monotonic-in-some-sense) structure. If you don't have that — a linked list, a stream, data you can only scan sequentially, or n small enough that O(n) and O(log n) are both instant — a plain linear scan is not a fallback, it's the correct tool. This is the same "brute force is sometimes just the right answer" principle from the Foundations and Backtracking topics, restated for search specifically. A sentinel linear search (append the target as an extra element past the end of the array before scanning, so the loop never needs a separate bounds check) is a small, classic micro-optimization worth recognizing by name even though modern compilers/branch predictors have mostly erased its practical benefit — it shows up in older textbooks (and the occasional systems-programming interview) as an example of removing a branch from a hot loop.

Square root decomposition: a middle ground before you reach for a segment tree

You already have a heavyweight answer to "range queries with point updates" — the Fenwick/segment tree machinery in the Trees topic. Square root decomposition is worth knowing as the simpler, "good enough" alternative: split the array into blocks of size √n, precompute an aggregate (sum, min, max) per block. A point update touches one element and its block's aggregate — O(1). A range query sums/combines the O(√n) fully-covered blocks plus scans the at-most-two partially-covered boundary blocks — O(√n).

class SqrtDecomposition:
    def __init__(self, arr):
        self.arr = arr[:]
        self.block_size = max(1, int(len(arr) ** 0.5))
        num_blocks = (len(arr) + self.block_size - 1) // self.block_size
        self.block_sum = [0] * num_blocks
        for i, val in enumerate(arr):
            self.block_sum[i // self.block_size] += val

    def update(self, index, value):
        self.block_sum[index // self.block_size] += value - self.arr[index]
        self.arr[index] = value

    def range_sum(self, lo, hi):  # inclusive
        total = 0
        i = lo
        while i <= hi:
            if i % self.block_size == 0 and i + self.block_size - 1 <= hi:
                total += self.block_sum[i // self.block_size]
                i += self.block_size
            else:
                total += self.arr[i]
                i += 1
        return total

When is a segment tree overkill? Sqrt decomposition trades a worse asymptotic bound (O(√n) vs. O(log n) per query) for a much simpler implementation with no recursive tree structure — for n in the range typical of interview constraints (10⁴–10⁶) and a modest number of queries, that trade is often the right one, and it's a perfectly legitimate thing to say out loud: "I could build a Fenwick tree here, but given the constraints, square root decomposition gets the same asymptotic query-update tradeoff shape with much less code — I'll reach for the tree if the interviewer tells me n or q is large enough to matter." Range Sum Query - Mutable (which you may have already solved with a Fenwick tree in the Trees topic) is solvable with exactly this technique instead — recognizing that the same problem has two valid solutions at different complexity/simplicity points is the actual skill being tested.

Binary search doesn't require a sorted array — it requires a monotonic predicate

This is the single most valuable reframe in this subtopic. Binary search's real precondition is: can you define a boolean predicate over the search space such that all "false" answers come before all "true" answers (or vice versa)? A literal sorted array is just the simplest case of a monotonic predicate (is arr[i] >= target). Once you see it this way:

Rotated sorted arrays aren't "unsorted" for this purpose — Search in Rotated Sorted Array (Binary Search Fundamentals) works because one specific monotonic predicate ("is this half the one containing the rotation point / target") still holds even though the raw array isn't in ascending order.
"Almost sorted" arrays (e.g., an array where each element is at most k positions from its sorted position) can sometimes still support a modified binary search or a bounded local search — the question to ask is always "what's the monotonic predicate here," not "is this literally sorted()-sorted."
Binary search on the answer space (the next subtopic) takes this to its logical conclusion: there's no array at all, just a monotonic feasibility function over a range of candidate answers.

Stating this explicitly — "binary search needs a monotonic predicate, not a literally sorted array" — is a strong signal in an interview when you're handed a structure that looks unsorted at first glance.

Galloping / exponential search: binary search when you don't know `n`

The problem: you have a sorted, indexable structure, but you don't know its length upfront — either because querying the length is expensive/impossible, or because it's conceptually unbounded (a stream, an S3 bucket you don't want to fully LIST).

The fix: find a valid upper bound cheaply by doubling — check index 1, then 2, then 4, then 8, ... until you either hit the target's range or a sentinel/out-of-bounds signal. Once you've overshot, you have a window [i/2, i] of size O(i) that's guaranteed to contain the answer (if it exists), and you binary search within that window normally.

def galloping_search(get, target):
    # get(i) returns the value at index i, or a sentinel signaling out-of-bounds
    if get(0) == target:
        return 0

    bound = 1
    while get(bound) < target:  # doubling until we overshoot
        bound *= 2

    lo, hi = bound // 2, bound
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if get(mid) >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo if get(lo) == target else -1

This costs O(log k) to find the bound (where k is the true position of the target) plus O(log k) for the binary search inside it — still O(log k) overall, just with roughly double the constant of a plain binary search on a known-length array. Find in Mountain Array and Search in a Sorted Array of Unknown Size are the LeetCode-shaped versions of this idea — both restrict direct access to an interface (get(i), often with a call budget), forcing you to combine "figure out the shape/bounds cheaply" with "binary search once you have them," exactly the two-phase structure above.

Real-world case study: finding the end of an append-only log without listing the bucket. A production system writes sequentially-numbered files to an append-only log (S3, GCS, a local log directory) — log-000001, log-000002, and so on — and a process needs to find the highest existing number after a crash, without an index of what exists. Listing the entire bucket (LIST) to find the max is expensive at scale (and, on S3 specifically, priced comparably to a PUT per page of results) and there's no known upper bound to binary search against directly. Galloping search solves this exactly as described: probe 1, 2, 4, 8, ... (a cheap existence check per probe, e.g. a HEAD request) until you find a number that doesn't exist, then binary search between the last-known-existing and first-known-missing numbers for the exact boundary. This is precisely the shape you already built for Time Based Key-Value Store (Binary Search Fundamentals) and its real-world analog — a versioned key-value store that remembers what value a key had at any point in time — generalized to a setting where you don't even know the candidate range upfront.

git bisect: binary search over commit history

git bisect is binary search applied to a version-control history instead of an array: given a known-good commit and a known-bad commit, and a way to test "is this commit good or bad" (your predicate), it bisects the range of commits between them, asks you (or a script) to test the midpoint, and narrows the range — finding the exact commit that introduced a regression in O(log n) tests instead of a linear bisection-by-hand. You already solved this exact shape of problem in First Bad Version (Binary Search Fundamentals) — recognizing "this is git bisect" the moment you see "there's a boundary between a good state and a bad state, and testing a candidate is expensive/slow" is a fast way to identify the pattern and communicate that recognition to an interviewer.

The lower bound: can you search faster than O(log n)?

For comparison-based search (you can only ask "is x less than, equal to, or greater than the target"), no — this is provable with the same decision-tree argument used for comparison-based sorting's Ω(n log n) lower bound: each comparison has 3 possible outcomes, so distinguishing among n possible positions requires at least ⌈log₂(n+1)⌉ comparisons in the worst case. Binary search achieves this bound exactly, so it's asymptotically optimal for the comparison model.

That said, two escapes are worth knowing about, precisely because "can we do better?" is a common interviewer follow-up:

Hash tables trade order for O(1) average. If you don't need the data ordered for anything else, a hash table answers "is x present" in O(1) expected time — it's not "faster binary search," it's a different model entirely (no comparisons, no ordering maintained), with the tradeoffs from the Probabilistic Algorithms & Data Structures topic (collisions, load factor, no range queries).
Interpolation search can do O(log log n) on uniformly distributed data. Instead of always checking the midpoint, it estimates where the target "should" be based on its value relative to the range's endpoints (like flipping to the right page of a phone book directly instead of always opening to the middle) — this beats binary search's O(log n) only when the data's distribution is known and roughly uniform; on adversarial or skewed data it degrades to O(n) worst case, which is precisely why it's a specialized technique rather than a default replacement for binary search.

Complexity summary

Technique	Time	Space	Use when
Linear / sentinel search	O(n)	O(1)	Unsorted, unindexable, streaming, or n too small to matter
Square root decomposition	O(1) update, O(√n) query	O(√n)	Range query + point update, when a Fenwick/segment tree is more machinery than the constraints justify
Binary search (known bounds)	O(log n)	O(1)	Sorted array or any monotonic predicate over a known range
Galloping / exponential search	O(log k) (k = target's position)	O(1)	Sorted but unbounded/unknown-length structure
Interpolation search	O(log log n) average, O(n) worst	O(1)	Uniformly distributed sorted data only

Pitfalls and interview gotchas

Assuming binary search needs a literally sorted array. State the monotonic-predicate reframe explicitly when handed a rotated, "almost sorted," or answer-space problem — this is the single highest-signal thing to say in this entire subtopic.
Forgetting the bound // 2 lower edge in galloping search. The window is [bound/2, bound], not [0, bound] — you already know everything below bound/2 failed the predicate on the previous doubling step, so re-scanning it wastes the exponential-search speedup entirely.
Reaching for a segment tree by default without considering whether sqrt decomposition's simplicity is worth the asymptotic tradeoff for the problem's actual constraints — this is a judgment call worth narrating, not a rule to follow blindly.
Claiming interpolation search is strictly better than binary search. It only wins on uniformly distributed data; volunteering the worst-case caveat unprompted is exactly the kind of nuance that separates "read about it once" from "understands the tradeoff."

How to talk about this in an interview

"I don't know the array's length, so I can't binary search directly — I'll gallop first: check index 1, 2, 4, 8, doubling until I overshoot the target, which gives me a window guaranteed to contain it, then binary search inside that window. Total cost is still O(log k) where k is the target's actual position, just with a slightly larger constant than a normal binary search."

"This isn't a sorted array, but binary search doesn't actually require that — it requires a monotonic predicate. Here, [state the predicate] is false-then-true across the range, so I can binary search on it directly even though the raw array isn't in ascending order."

Further Resources (Optional)

GeeksforGeeks — Exponential SearchArticle12m
GeeksforGeeks — Square Root (Sqrt) Decomposition AlgorithmArticle20m
Git Documentation — git-bisectReference12m
GeeksforGeeks — Unbounded Binary Search (find the point where a monotonic function turns positive)Article12m
GeeksforGeeks — Interpolation SearchArticle12m
Wikipedia — Decision Tree Model (comparison lower bounds for sorting and searching)Reference10m

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Search in a Sorted Array of Unknown SizeMediumPremium!2/520m
Find in Mountain ArrayHard!4/535m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Guess Number Higher or LowerEasy!1/515m