On the Complexity of Searching a Set of Vectors
D. S. Hirschberg · SIAM Journal on Computing · 1980
The vector searching problem is, given k-vector A (a k-vector is a vector that has k components, over the integers) and given a set $\bar B$ of n distinct k-vectors, to determine whether or not A is a member of set $\bar B$. Comparisons between components yielding “greater than-equal-less than” results are permitted. If the vectors in $\bar B$ are unordered then $nk$ comparisons are necessary and sufficient. In the casewhen the vectors in B are ordered, it is shown that $\lfloor \log n \rfloor + k$ comparisons are necessary and, for $n \geqq 4k$, $k\lceil\log (n/k) \rceil + 2k - 1$ comparisons are sufficient.