Uniform Search – An intelligent and better search on sorted data

Copyright (c) 2008 by Gagandeep Singh
This material may be distributed only subject to the terms and conditions set forth in the Open Publication License,
v1.0 or later (the latest version is presently available at http://www.opencontent.org/openpub/).

I appreciate the concept of binary searching, divide and search. It gives significant boost over linear search. It gives searching more natural look, i.e., it search resembles more like human beings’ searching, but not exactly the same. And we know that we can search faster than machines. Oh, I really don’t mean by time wise but the number of passes machine took to complete the task and number of passes we took to complete that task. What I really means that some humans are really smarter than the machine, because they can learn and bettered that approach.

Now come to complete off track from previous one. What happened in the history? I really don’t know. But assume that we shed all our weapons of innovation to the great searching (binary search) and concentrate more on sorting and sorting & searching mixed (binary search trees, B-trees, B+ trees, etc.). We do things that were fascinating but forget to provide basic foundation right. Oh! You want to hit me because of that line. Just hit me. Because time needs change and we cannot stick to old chair, if it was crumbling. If you do that then you are only responsible for results, don’t blame me for that. I am very irresponsible person, who makes furniture with an axe. I just do things. Team has plans. Professionals have plans. Organizations’ got the plans. They're schemers. Schemers trying to improve their little worlds. I'm not a schemer. I try to show the schemers how pathetic their attempts to improve things really are. So... When I say that I’ve better method than binary search. You know that I'm telling the truth.

Now get into real business. The method of new searching called Uniform Search. Because it assumes that data is uniformly distributed over the entire interval. And based on that determine where the intermediate element should be. In binary search intermediate element always in middle, but in Uniform Search based on lower value, upper value, and number of elements intermediate element is decided. This concept is more like Humans, o.k. as far as I am concern and I believe that I am Human. If I had a book, definitely I had, with 1000 pages and 10 chapters and need to open 3^rd chapter. Then I open page number 201 first. Assuming uniform distribution, it means that every chapter took 100 pages. And if it is 7^th chapter then according to so called uniform distribution, that is certainly not here, the 3^rd chapter is between 1 to 200 pages and 1 to 7 chapters. So, it must be somewhere

(200/7)*3=600/7=85(floor value of 85.71)

Hence, I now open page number 85. May be I am lucky to find the chapter, but surely I am tired to carried on this example.

But, one thing you would like. The comparison between Uniform search and binary search:

Comparison between Uniform Search and Binary Search

This graph show how data of 100 numbers searched for each number in the data list. And it plots number of passes of binary search and uniform search.

You can download the program fragment Uniform Search.