## Binary search algorithm & trace

Binary search efficiently searches an array to find a given key. The array must already be sorted for the algorithm to work.

For the example traces below, the algorithm returns the position of `key`

in `arr`

or `-1`

if `key`

is not in `arr`

. A more sophisticated return value when `key`

is not found is featured below in the Binary search with insertion point return section.

### Example 1

#### Step 1

```
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 0
high: 9
```

`arr`

and `key`

are parameters. `low`

and `high`

(sometimes called `start`

and `end`

) are indexes that represent the bounds of the part of the array that remains to be searched. The initial values of `low`

and `high`

are `0`

and `arr.length - 1`

, respectively.

#### Step 2

The value of `mid`

is the average of `low`

and `high`

, calculated using integer division (drop any decimal portion).

```
mid: 4
```

`key`

(35) is less than `arr[mid]`

(71). If `key`

is in `arr`

, it must be to the left of `mid`

. The value of `high`

is updated to `mid - 1`

. The value of `low`

remains the same.

```
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 0
high: 3
```

#### Step 4

```
mid: 1
```

`key`

(35) is greater than `arr[mid]`

(24). `low`

is updated to `mid + 1`

.

```
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 2
high: 3
```

#### Step 5

```
mid: 2
```

`key`

(35) is equal to `arr[mid]`

. The algorithm stops and returns `mid`

(2), which is the position of `key`

in `arr`

.

### Example 2

```
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 86
```

`low` |
`high` |
`mid` |
---|---|---|

`0` |
`9` |
`4` |

`5` |
`9` |
`7` |

`8` |
`9` |
`8` |

The algorithm returns 8, a position of 86 in `arr`

.

In this example, the algorithm happened to find the first 86 in the array. This is not always the case. If asked what is returned when executing binary search on an array with more than 1 copy of `key`

, trace the algorithm to find the specific index returned.

### Example 3

```
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 40
```

`low` |
`high` |
`mid` |
---|---|---|

`0` |
`9` |
`4` |

`0` |
`3` |
`1` |

`2` |
`3` |
`2` |

`3` |
`3` |
`3` |

`4` |
`3` |
not computed |

On the last step, `low`

is greater than `high`

. This means there are 0 elements in the part of the array left to search, so `key`

is not in `arr`

.

On the step above, `low == high`

. We cannot stop just because `low == high`

. There is still 1 element to check.

## Binary search implementations

### Recursive binary search

```
private static int binarySearch(int[] arr, int key, int low, int high)
{
if (low > high)
return -1;
int mid = (low + high) / 2;
if (key < arr[mid])
return binarySearch(arr, key, low, mid - 1);
else if (key > arr[mid])
return binarySearch(arr, key, mid + 1, high);
else
return mid;
}
public static int binarySearch(int[] arr, int key)
{
return binarySearch(arr, key, 0, arr.length - 1);
}
```

Binary search is easy to implement recursively. The private method takes the parameters necessary to constrain the search to part of the array. The public method takes the parameters appropriate for a search method.

As mentioned above, the precondition for binary search is that the array is sorted.

### Iterative binary search

```
public static int binarySearch(int[] arr, int key)
{
int low = 0;
int high = arr.length - 1;
while(low <= high)
{
int mid = (low + high) / 2;
if (key < arr[mid])
high = mid - 1;
else if (key > arr[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
```

The iterative implementation of binary search creates `low`

and `high`

as local variables instead of as parameters.

### Binary search with insertion point return

```
public static int binarySearch(int[] arr, int key, int low, int high)
{
if (low > high)
return -low - 1;
int mid = (low + high) / 2;
int result = key - arr[mid];
if (result < 0)
return binarySearch(arr, key, low, mid - 1);
else if (result > 0)
return binarySearch(arr, key, mid + 1, high);
else
return mid;
}
```

The version of binary search above is identical to the original except that it returns a more sophisticated value when `key`

is not found in `arr`

. A simple version of binary search returns `-1`

when `key`

is not found in `arr`

. Since `arr`

is sorted, there is additional information available when `key`

is not found. Specifically, the algorithm knows the position at which `key`

would need to be inserted into `arr`

to maintain the sorted order. This position is known as the insertion point.

If `low > high`

(the base case) the insertion point is `low`

. The method above returns `-low - 1`

. This allows for quick examination of the return value to determine if `key`

was found. (A negative return value indicates that `key`

was not found.) It also allows for quick convertion to the actual insertion point if desired.

Problem #10 in the 2014 AP CS A Course Description sample multiple choice makes use of a variant of the above. The variant in the problem returns the actual insertion point (`low`

) rather than a modified version of it (`-low - 1`

).

One of my insertion sort variants calls the method above to determine where to insert the element into the sorted part.

### Binary search with `ArrayList<String>`

```
public static int binarySearch(ArrayList<String> list, String key, int start, int end)
{
if (start > end)
return -start - 1;
else
{
int mid = (start + end) / 2;
int result = key.compareTo(list.get(mid));
if (result < 0)
return binarySearch(list, key, start, mid - 1);
else if (result > 0)
return binarySearch(list, key, mid + 1, end);
else
return mid;
}
}
```

This is nearly identical to the variant above, except it uses `compareTo`

. The result of the call to `compareTo`

is stored in `result`

to avoid calling `compareTo`

twice.

For more about how to handle `compareTo`

on the AP CS A Exam, see compareTo on the AP CS A Exam.