In a sorted array, why does counting a value by one binary search plus an outward scan degrade to O(n)?
answer
- count the elements the walk actually touches
- the cost has two terms, not one
- which term grows with the skew
- duplicates are why you asked in the first place
- two boundary searches, then subtract the indices
basics
~20 sWalking outward from a match touches one element per duplicate, so counting costs O(log n + k) for a run of k equal keys, and k grows with the very skew that motivated the query. Two boundary searches stay O(log n).
solid answer
~50 sFinding any match is logarithmic, but walking outward to the run's edges costs one step per duplicate, so the true bound is O(log n + k) where k is how many copies exist. Calling that "still logarithmic" is the mistake: on skewed data k dominates. Take a metrics store of a billion samples sorted by status code where almost everything is a success code — counting one code by scan-out touches hundreds of millions of entries, faulting in pages the whole way. Running two boundary searches instead, one for the first index and one for the last, gives the count as `last - first + 1` in O(log n) total with no dependence on run length, and hands back the slice bounds for free. Scan-out is only defensible when runs are known to be short or the caller must visit every match anyway.
go deeper
Be ready to say that walking outward from a match costs one step per duplicate, so the total is the search plus the run length. Knowing the count is last minus first plus one, inclusive on both ends, is the concrete takeaway.
Explain why the two terms cannot be collapsed: which one dominates is decided by the data, and duplicates are the premise of the question. Show that two boundary searches stay logarithmic even when every element matches.
Demonstrate the production instinct: the same code is fast for rare values and catastrophic for common ones, which reads as a bimodal latency profile driven by input skew rather than by size. Say how you would confirm it and what you would measure.
Own the standard, not the fix. Decide whether run length is bounded by the data model or merely by today's data, and prefer the variant with no dependence on skew when nothing enforces the bound — an assumption in a comment is not a constraint.
## The cost model, stated honestly Let `n` be the array length and `k` the number of elements equal to the target — the length of the contiguous run. Two strategies: | strategy | cost | depends on k? | |---|---|---| | find any match, walk both ways to the run's edges | O(log n + k) | yes | | two boundary searches, count = `last - first + 1` | O(log n) | no | The defect in the first row is not that the bound is wrong; it is that people quote it as O(log n) and drop the `k`. Big-O addition does not let you discard a term because the other one looks impressive. Whichever term dominates depends on the data, and the whole reason someone asks for first and last occurrence is that duplicates are expected — so `k` being large is the *normal* case, not the pathological one. ## Where it bites Consider a metrics store: a billion request samples held sorted by status code, with the overwhelming majority successes and a long thin tail of error codes. Two queries arrive. - *Count the error code.* The run is small, maybe a few thousand entries. Scan-out is fine; the walk is invisible next to the search. - *Count the success code.* The run is most of the array. Scan-out walks hundreds of millions of entries — cache-missing, page-faulting, and turning a microsecond query into a multi-second one. Same code, same array, two orders of magnitude apart in cost, decided entirely by which value the caller passed. That is the shape of the bug that gets shipped: it is fast in the test fixture, fast for the queries the author had in mind, and catastrophic for the query someone else writes six months later. It shows up as a bimodal latency distribution — a tight p50 and a p99 in another unit — because the tail is not noise, it is a different code path length driven by input skew. The follow-up an interviewer uses to expose it is deliberately blunt: *what if 40% of the array is the target?* If the answer is "still logarithmic, binary search is logarithmic", the candidate has not internalised that the scan is a separate term. ## The two-search alternative Run the leftmost-occurrence search and the rightmost-occurrence search independently. Each is O(log n) and each is insensitive to `k` — even an array consisting *entirely* of the target takes logarithmically many iterations, because each equality hit halves the interval instead of stepping one element. Then: - absent target: the first search reports nothing found, count is zero, and the second search need not run at all; - present target: `count = last - first + 1`. The off-by-one in that arithmetic is the classic slip — both endpoints are inclusive, so the difference alone undercounts by exactly one. Sanity-check it against a run of length one, where `first == last` and the count must be 1. A second benefit often matters more than the count: the pair `(first, last)` is a *slice descriptor*. Anything you wanted to do with the matches — take a contiguous view, copy them, page through them, delete the range — is now expressible in terms of two indices rather than a search plus a walk. Mainstream standard libraries, C++'s and Python's among them, expose paired boundary primitives rather than a single find-the-target call precisely because the range is what callers actually want. ## When scan-out is genuinely fine Being asymptotically worse does not make it wrong everywhere; asymptotic superiority promises nothing at small sizes, and constants decide there. - **The caller must touch every match anyway.** If the job is to sum a field over all matching rows, you are paying Ω(k) regardless. Even then, take the boundaries first and iterate the slice — you get the same work with a known bound and no edge-detection logic. - **Runs are provably short.** If the key is nearly unique — a timestamp with millisecond resolution, a monotonically increasing identifier — `k` is one or two and a second search costs more than the walk. - **The array is tiny.** Below a few dozen elements the whole question is noise, and a linear pass may beat both. What turns these from judgment into hazard is when the bound on `k` is an assumption rather than a property. "Duplicates are rare in this table" is a statement about today's data, not about the schema. If nothing enforces it, the cost is one skew event away from becoming linear. ## How to decide, and how to verify Measure the **distribution** of run lengths, not the average. An average run length of 1.3 is entirely consistent with one value occupying 40% of the array, and it is that value's queries that will define the tail latency. If the maximum run length is unbounded by anything but the data, use the two searches — the constant factor of a second logarithmic search is a rounding error against the risk, and it removes an entire failure mode instead of documenting it.
- What if 40% of the array is the target value?Then the outward walk touches roughly 0.4n elements and the query is linear in everything but name; the logarithmic search in front of it is noise. Two boundary searches are unaffected — each still runs about log2 n iterations, because an equality hit halves the interval instead of stepping one element. This is the case that separates a candidate who quotes the bound from one who has reasoned about it.
- Given first and last, how do you get the count, and where is the off-by-one?`count = last - first + 1`, because both endpoints are inclusive. Omitting the `+ 1` undercounts by exactly one for every run, which is easy to miss on large data and obvious on a run of length one, where `first == last` and the answer must be 1. Keep a single-occurrence case in the test table for exactly this reason.
- Is there a case where you'd still walk outward from a single hit?Yes — when the caller has to visit every match anyway, or when the key is nearly unique so runs are one or two long and a second search costs more than the walk. The distinction is whether the bound on run length is enforced by the data model or merely observed today. If nothing enforces it, take the boundaries; the extra logarithmic search removes a failure mode rather than documenting it.
- How would you confirm the scan is what's driving a bimodal latency profile?Correlate latency with the queried key's run length rather than with array size — the tail should track how many duplicates that particular value has, not how big the store is. A fast p50 with a p99 in a different unit, split cleanly by which value was queried, is the signature. Counting elements visited per query makes it unambiguous.
saying these in an interview costs you the question
- Says it is still O(log n) because binary search is logarithmic
- Drops the k term from O(log n + k) as negligible
- Computes the count as last minus first
- Assumes duplicates are rare without anything enforcing it
- Reasons from average run length instead of the maximum