## Section 9.6 Array Algorithms: Searching

Suppose we have a large array and we need to find one of its elements. We need an algorithm to search the array for a particular value, usually called the key. If the elements of the array are not arranged in any particular order, the only way we can be sure to find the key, assuming it is in the array, is to search every element, beginning at the first element, until we find it.

### Subsection 9.6.1 Sequential Search

This approach is known as a sequential search, because each element of the array will be examined in sequence until the key is found (or the end of the array is reached). A pseudocode description of this algorithm is as follows:

#### Algorithm 9.6.1. Sequential search.

```
1. For each element of the array
2. If the element equals the key
3. Return its index
4. If the key is not found in the array
5. Return -1 (to indicate failure)
```

This algorithm can easily be implemented in a method that searches an integer array, which is passed as the method's parameter. If the key is found in the array, its location is returned. If it is not found, then \(-1\) is returned to indicate failure.

The `Search`

class (FigureÂ 9.6.2 and ListingÂ 9.6.3) provides the Java implementation of the `sequentialSearch()`

method. The method takes two parameters: the array to be searched and the key to be searched for. It uses a for statement to examine each element of the array, checking whether it equals the key or not. If an element that equals the key is found, the method immediately returns that element's index. Note that the last statement in the method will only be reached if no element matching the key is found.

#### Principle 9.6.4. EFFECTIVE DESIGN: Sentinel Return Value.

Like Java's `indexOf()`

method, the `sequentialSearch()`

returns a sentinel value (\(-1\)) to indicate that the key was not found. This is a common design for search methods.

### Subsection 9.6.2 Binary Search

If the elements of an array have been sorted into ascending or descending order, it is not necessary to search sequentially through each element of the array in order to find the key. Instead, the search algorithm can make use of the knowledge that the array is ordered and perform what's known as a binary search, which is a divide-and-conquer algorithm that divides the array in half on each iteration and limits its search to just that half that could contain the key.

To illustrate the binary search, recall the familiar guessing game in which you try to guess a secret number between 1 and 100, being told â€śtoo highâ€ť or â€śtoo lowâ€ť or â€śjust rightâ€ť on each guess. A good first guess should be 50. If this is too high, the next guess should be 25, because if 50 is too high the number must be between 1 and 49. If 50 was too low, the next guess should be 75, and so on. After each wrong guess, a good guesser should pick the midpoint of the sublist that would contain the secret number.

Proceeding in this way, the correct number can be guessed in at most \(log_2 N\) guesses, because the base-2 logarithm of *N* is the number of times you can divide *N* in half. For a list of 100 items, the search should take no more than seven guesses (\(2^7 = 128 > 100\)). For a list of \(1,000\) items, a binary search would take at most ten guesses (2\(^{10}=1,024>1,000\)).

So a binary search is a much more efficient way to search, provided the array's elements are in order. Note that â€śorderâ€ť here needn't be numeric order. We could use binary search to look up a word in a dictionary or a name in a phone book.

A pseudocode representation of the binary search is given as follows:

#### Algorithm 9.6.5. Binary search.

```
TO SEARCH AN ARRAY OF N ELEMENTS IN ASCENDING ORDER
1. Assign 0 low and assign N-1 to high initially
2. As long as low is not greater than high
3. Assign (low + high) / 2 to mid
4. If the element at mid equals the key
5. then return its index
6. Else if the element at mid is less than the key
7. then assign mid + 1 to low
8. Else assign mid - 1 to high
9. If this is reached return -1 to indicate failure
```

Just as with the sequential search algorithm, this algorithm can easily be implemented in a method that searches an integer array that is passed as the method's parameter (ListingÂ 9.6.3).

If the key is found in the array, its location is returned. If it is not found, then \(-1\) is returned to indicate failure. The `binarySearch()`

method takes the same type of parameters as `sequentialSearch()`

. Its local variables, `low`

and `high`

, are used as pointers, or references, to the current low and high ends of the array, respectively.

Note the loop-entry condition: `low <= high`

. If `low`

ever becomes greater than `high`

, this indicates that `key`

is not contained in the array. In that case, the algorithm returns \(-1\text{.}\)

As a binary search progresses, the array is repeatedly cut in half and `low`

and `high`

will be used to point to the low and high index values in that portion of the array that is still being searched.

The local variable `mid`

is used to point to the approximate midpoint of the unsearched portion of the array. If the key is determined to be past the midpoint, then `low`

is adjusted to `mid+1`

; if the key occurs before the midpoint, then `high`

is set to `mid-1`

. The updated values of `low`

and `high`

limit the search to the unsearched portion of the original array.

Unlike sequential search, binary search does not have to examine every location in the array to determine that the key is not in the array. It searches only that part of the array that could contain the key. For example, suppose we are searching for \(-5\) in the following array:

```
int sortArr[] =
{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
```

The \(-5\) is smaller than the smallest array element. Therefore, the algorithm will repeatedly divide the low end of the array in half until the condition `low > high`

becomes true. We can see this by tracing the values that low, mid, and high will take during the search:

As this trace shows, the algorithm examines only four locations to determine that \(-5\) is not in the array. After checking location 0, the new value for `high`

will become \(-1\text{,}\) which makes the condition `low <= high `

false. So the search will terminate.

The `TestSearch`

class (FigureÂ 9.6.7 and ListingÂ 9.6.8) provides a program that can be used to test two search methods. It creates an integer array, whose values are in ascending order. It then uses the `getInput()`

method to input an integer from the keyboard and then performs both a `sequentialSearch()`

and a `binarySearch()`

for the number.

#### Exercises Self-Study Exercise

##### 1. Binary search.

Suppose we use binary searchÂ 9.6.5 to search for 21 in the following array of numbers:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 subscripts 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 values

Which of the following shows the value of mid on each iteration of the search?

7, 11, 9, 8

Incorrect

7, 10, 8, 9

Incorrect

7, 10, 8, 9

Incorrect

6, 10, 8, 9

Correct.