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.