Monday, May 17, 2010

Super Quick Search

Binary search divides the search area into 2 partitions recursively and finds the value.

There is a better and faster way to search for a value.

When searching a value in an array of n numbers,

NB: Reals are rounded down to the nearest int and are ommited.

Divide it into n(1) = sqrt(n(0)) partitions of n(1) = sqrt(n(0))

Continue dividing each set of partitions of size n(i) into partitions n(i + 1) = sqrt(n(i)) of the approx. same size until narrowed to n(k) such that log2 (n(k)) <= sqrt(n(k)) + n(k) ^(1/4) + n(k) ^ (1/8) ... + 2 or 3 items recursively.

If subsiquant partitions where log2 (n(k)) > sqrt(n(k)) + ... are encountered select appropriate partition value fall into else repeat above other wise do a binary search.