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. 

1 Comments:

Blogger Suminda Sirinath Salpitikorala Dharmasena said...

Second thoughts the time complexity will be the same as binary search with additional space complexity.

Monday, 17 May 2010 at 10:29:00 GMT+5:30  

Post a Comment

Subscribe to Post Comments [Atom]

Links to this post:

Create a Link

<< Home