The k-vector search technique is a general purpose search method that is capable of locating entries in a sorted array with complexity independent from the database size. It is based on an m-long vector of integers, called the k-vector, that keeps record of the sorted database nonlinearities. The traditional k-vector best performs for almost linear sorted databases. In this paper we extend the k-vector technique by the use of non-linear mapping functions, and show how this approach can potentially solve performance and memory limitations of the traditional k-vector for searches in arrays with strongly non-uniform distributions.
