Searching Arrays in C++

If an array is sorted, binary search is more efficient than linear search for finding an element in the array.

Searching is the process of looking for a specific element in an array—for example, discov­ering whether a certain score is included in a list of scores. Searching is a common task in computer programming. Many algorithms and data structures are devoted to searching. This section discusses two commonly used approaches: linear search and binary search.

1. The Linear Search Approach

The linear search approach compares the key element key sequentially with each element in the array. The function continues to do so until the key matches an element in the array or the array is exhausted. If a match is made, the linear search returns the index of the element in the array that matches the key. Otherwise, the search returns -1. The linearSearch function in Listing 7.9 gives the solution:

Listing 7.9 LinearSearch.cpp

int 1inearSearch(const int 1ist[], int key, int arraySize)

{

for (int i = 0; i < arraySize; i++)

{

if (key == list[i])                                                             

return i;                                                               

}

return -1;                                                                

}

Please trace the function using the following statements:

int list[] = {1, 4, 4, 2, 5, -3, 6, 2};

int i   = linearSearch(list,  4, 8); // Returns   1

int j  =  linearSearch(list, -4, 8);  // Returns -1

int k =  linearSearch(list, -3, 8);  // Returns 5

The linear search function compares the key with each element in the array. The elements in the array can be in any order. On average, the algorithm will have to compare half of the elements before finding the key if it exists. Since the execution time of a linear search increases linearly as the number of array elements increases, linear search is inefficient for a large array.

2. The Binary Search Approach

Binary search is the other common search approach for a list of values. It requires that the elements in the array already be ordered. Assume that the array is in ascending order. The binary search first compares the key with the element in the middle of the array. Consider the following cases:

• If the key is less than the middle element, you only need to continue to search in the first half of the array.
• If the key is equal to the middle element, the search ends with a match.
• If the key is greater than the middle element, you only need to continue to search in the second half of the array.

Clearly, the binary search function eliminates at least half of the array after each compari­son. Sometimes you eliminate half of the elements, and sometimes you eliminate half plus one. Suppose that the array has n elements. For convenience, let n be a power of 2. After the first comparison, n/2 elements are left for further search; after the second comparison, (n/2)/2 elements are left for further search. After the k^th comparison, n/2^k elements are left for further search. When k = log₂n, only one element is left in the array, and you need only one more comparison. In the worst case, therefore, when using the binary search approach, you need log₂n+1 comparisons to find an element in the sorted array. In the worst case, for a list of 1024 (2¹⁰) elements, binary search requires only eleven comparisons whereas a linear search requires 1024. The portion of the array being searched shrinks by half after each com­parison. Let low and high denote, respectively, the first index and last index of the subarray. Initially, low is 0 and high is listSize-1. Let mid denote the index of the middle element. So mid is (low + high)/2. Figure 7.6 shows how to find key 11 in the list {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79} using binary search.

Figure 7.6 Binary search eliminates half of the list from further consideration after each comparison.

You now know how the binary search works. The next task is to implement it. Don’t rush to give a complete implementation. Implement it incrementally, one step at a time. You may start with the first iteration of the search, as shown in Figure 7.7a. It compares the key with the middle element in the list whose low index is 0 and high index is listSize – 1. If key < list[mid], set the high index to mid – 1; if key == list[mid], a match is found and return mid; if key > list[mid], set the low index to mid + 1.

Next, consider how to implement the function to perform the search repeatedly by adding a loop, as shown in Figure 7.7b. The search ends if the key is found or the key is not found. Note that when low > high the key is not in the array.

When the key is not found, low is the insertion point where a key would be inserted to maintain the order of the list. It is more useful to return the insertion point than -1. The func­tion must return a negative value to indicate that the key is not in the list. Can it simply return -low? No. If key is less than list[0], low would be 0. -0 is 0. This would indicate that key matches list[0]. A good choice is to let the function return -low – 1 if the key is not in the list. Returning -low – 1 not only indicates that the key is not in the list, but also where the key would be inserted in the list.

The binary search function is implemented in Listing 7.10.

Listing 7.10 BinarySearch.cpp

1 int binarySearch(const int list[], int key, int listSize)
2 {
3    int low = 0;
4    int high = listSize – 1;
5
6    while (high >= low)
7    {
8       int mid = (low + high) / 2;
9       if (key < list[mid])
10         high = mid – 1;
11      else if (key == list[mid])
12         return mid;
13      else
14          low = mid + 1;
15    }
16
17    return -low – 1;
18 }

The binary search returns the index of the search key if it is contained in the list (line 12). Otherwise, it returns -low – 1 (line 17). What happens if (high >= low) in line 6 is replaced by (high > low)? The search would miss a possible matching element. Consider a list with just one element. The search would miss the element. Does the function still work if there are duplicate elements in the list? Yes, as long as the elements are sorted in non­decreasing order in the list. The function returns the index of one of the matching elements if the element is in the list.

To understand this function better, trace it with the following statements and identify low and high when the function returns.

int list[] = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
int i = binarySearch(list, 2, 13); // Returns 0
int j = binarySearch(list, 11, 13); // Returns 4
int k = binarySearch(list, 12, 13); // Returns –6
int l = binarySearch(list, 1, 13); // Returns –1
int m = binarySearch(list, 3, 13); // Returns –2

Here is the table that lists the low and high values when the function exits and the value returned from invoking the function.

Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.