= 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}\leq\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.
Back to article page
