 Missing-value search by deficient value intervals

Suppose a candidate integer interval contains $W$ possible values and an active array segment contains exactly all occurrences from that interval, with $m<W$ entries. The pigeonhole principle guarantees a missing value. Split the value interval into widths $W_L,W_R$ and use array partitioning to obtain occurrence counts $m_L,m_R$. If $m_L<W_L$, retain the left side. Otherwise $m_R=m-m_L<W-W_L=W_R$, so retain the right side. This works with duplicate entries because it needs only the inequality between occurrences and possible values.

Balancing the value widths gives $W_{i+1}\le \lceil W_i/2\rceil$, while the active scan length remains less than $W_i$. The total work is bounded by a geometric series and logarithmic loop overhead, hence $O(W_0)$ time complexity. On reaching width one, the retained occurrence count is zero, proving that the sole candidate is absent globally. This is a binary search over deficient value intervals, with local in-place array partitioning, rather than repeated full-array scans.