Efficiently Searching Lists using Binary Search

In programming, often we find ourselves working with large sets of data. A lot of this work is reliant on matching up data, and searching the data for specific values. A good understanding of different search techniques is essential in order to minimize processing time.

To start, let’s consider a small data set, which we will call testSet. I will define the data set as follows:

Suppose I want to search this list for a specific value. One strategy might be to do the following:

We call this a linear search. This search will iterate the list one element at a time, looking for the value that is being searched for. If it is found, the index of the element is returned. If it is not found, -1 is returned to indicate the value is not in the list.

Breaking down this algorithm further, we can see that in the worst case we need to look at every single element in the list. So, if our list has n elements in it, we need to search n times, meaning the algorithm efficiency is O(n).

To see how we can do better than this, we introduce the concept of a binary search. In order for a binary search to work, the list must be sorted before we search it. The binary search algorithm looks like this: