Search arrays and files using a Binary Search
There is no faster way to search a list for an item than a binary search.
Each search attempt cuts your list in half. The result: it takes only about 2 dozen tries to find an item
in a 1 million item list. A 2 million item list takes only one more attempt. This example explains how the
binary search works.
Download Source Code
Typically to search a list you start at one end and check each item sequentially
until you find a match or reach the end of the list. This is easy to code but very
inefficient with large lists. It takes ten thousand iterations to find the last
item in a ten thousand item list. The binary search requires at most 15
attempts - much better.
The caveat is the list must be sorted. Hopefully you can retrieve it in the
proper order from your database query or you can sort it programmatically using a
quick sort or bubble sort.
Worst case you can add the items to a listbox whose sorted property is set True.
The binary search looks to the middle of a list for a
match. If a match is found, you are done. If not, it checks if the middle item is
greater than the item you are looking for. If so, you know the item must reside in the
first half of the list. The second half of the list is ignored. Only the first half
will be examined on the next search attempt. Conversely, if the middle item was less than the
search string, the first half of the list would have been discarded.
Each search pass cuts the list in half. This results in the binary search's speed but also
poses a few problems. The search utilizes pointers to the beginning, end and middle of the
list. You cannot have a pointer to the middle item if the list has an even number of elements.
Also, you cannot divide a list with an odd number of items into two equal halves. The code
must accommodate these scenarios.
Additionally, a one item list must be handled. In this case, the code simply checks to
see if the item is the one you are looking for.
Download this project and run it. Select a customer ID from the list and click the
appropriate button to either search a file of customer information or an array of
the same information for the matching record.