1.3 Case study: Linear and binary search in arrays

One of the most fundamental tasks that we use computers for is searching. We want to find an object that matches some criteria, in a collection of objects. In fact, most of the data structures and algorithms that we will present in this book have to do with searching in some way – how to store data so that we can retrieve them easily, and how to find the data we are interested in.

One way of storing a collection of objects is to put them in an array. So, assuming that we have an array of objects, how can we find a certain object in this array?

To turn this algorithm into actual code, we need to decide how to represent the search interval in computer memory. The operation of excluding elements from the interval needs to be fast – making a new smaller array is too slow. Instead we define the interval by the lower and upper indices it includes, so (10,24) would represent the interval from index 10 to and including index 24 (15 elements). The middle element is (10+24)/2=17 (rounding down when needed). Searching the lower half just means altering the interval to (10,16), and the upper half (18,24). Here is an implementation of binary search that does not only say if the key is in the array, but also at which index it resides (or null if it is absent):

binarySearch(arr, key):
    start = 0                      // The index of the first element in the interval
    end = arr.size - 1             // The index of the last element in the interval
    while start <= end:            // Continue until the interval is empty:
        mid = (start + end) / 2    //     Find the index of the middle value
        if arr[mid] < key:         //     Compare with the middle value in the interval:
            start = mid + 1        //         The search key is in the upper half
        else if arr[mid] > key:
            end = mid - 1          //         The search key is in the lower half
        else: // (here arr[mid]==key)
            return mid             //         We found the search key!
    return null                    // The value is not in the array.

An important technical detail here is that \mathit{mid} = (\mathit{start} + \mathit{end}) / 2 is understood to use integer division, so (6+11)/2 is 8, not 8.5. Consider how this implementation deals with corner cases, for instance when the search area has a single element (when \mathit{start}=\mathit{end}). Or when it has two elements. Does it calculate \mathit{mid} correctly and yield correct result in these cases?

In this particular implementation we use inclusive indices, both \mathit{start} and \mathit{end} are inside the area. Another common option is to have \mathit{start} be inclusive, and \mathit{end} exclusive (so the starting interval is (0,\mathit{arr.size})). Yet another option is to have a start index and a size of the interval. Each variation would do slightly different calculations, but require the same fundamental building operations: Finding the middle element, and excluding the upper/lower half of the interval. Figure 1.1 illustrates an example search of a small array.

Figure 1.1: Steps of Binary search for the value D in a sorted array of length 9, revealing elements as they are compared to D. After three comparisons, the search interval is empty, D is not in the array.

There are many variations of binary search. If the array had books sorted by number of pages, we could use it to find books of a desired length, or even all books in a precise range of pages. Consider what would happen if the array was not sorted properly, can you construct a small example where the algorithm would go wrong? Also consider, could binary search be used to determine if an array contains a prime number?

Here is an illustration of the binary search algorithm.