# Binary Search

## Contents

# 15.2. Binary Search#

Searching for an element in a sorted array is quick. Think of having a pile of booklets with names sorted in ascending order. Say you want to find the booklet with the name “Snefru”. You can start at the middle of the pile and check if the name is “Snefru”. If it is, you are done. If it is not, you can check if the name is before or after “Snefru”. If it is before, you can discard the second half of the pile. If it is after, you can discard the first half of the pile. You can repeat this process until you find the booklet with the name “Snefru”.

This method that we just discussed is called binary search. It is called binary search because it searches the list in a binary fashion, checking the middle element of the list and then discarding **half** of the list based on the result.

Given an array of seven elements named `list`

as shown in the figure below, we want to look for `item`

\(9\).

The algorithm for binary search is as follows:

Define the limits of the array using variables

`low`

and`high`

. We can do so by initially setting`low = 0`

and`high =`

length of array`- 1`

. Since we want to look at the middle element, we can hold its index in`middle = (low + high)/2`

.Since the value at index

`middle`

is not equal to`item`

, which is`9`

, we need to continue looking for`item`

. We can check if`list[middle] < item`

. If it is, we can discard the first half of the list. If it is not, we can discard the second half of the list. In our case,`list[middle]`

is 7, which is less than`item`

, which is`9`

. Therefore, we can discard the first half of the list. We can do this by setting`low = middle + 1`

.We can repeat step \(1\) and \(2\) but on the smaller right sub-array until we find

`item`

. In our case,`low`

is`4`

and`high`

is`6`

. This makes`middle = 5`

. Since`list[middle]`

is`10`

, which is less than`item`

, which is`9`

, next we can discard the second half of the sub-array (after middle).We can discard the second half of the sub-array by setting

`high = middle - 1`

. After discarding the second half of the array, we have`low = 4`

and`high = 4`

. This makes`middle = 4`

.Since

`list[middle]`

is`9`

, which is equal to`item`

, we have found`item`

in the array.

When not found!

If `item`

in our example was `8`

, we would **NOT** have found it at index `4`

. However, the algorithm will continue with setting `high = middle - 1`

. This would make `high = 3`

, and `low`

remains `4`

. The algorithm should terminate when `low > high`

. This means that the algorithm has searched the entire array and has not found `item`

.

## 15.2.1. Pseudocode#

To highlight the main steps of binary search, we can write the algorithm in pseudocode as follows:

Set

`low = 0`

and`high`

to the length of the array - 1.Look at the element at index

`middle = (low + high)/2`

.If the element at index

`middle`

is equal to`item`

, return`middle`

.If the element at index

`middle`

is less than`item`

, the`item`

could be in the right sub-array. Set`low = middle + 1`

to look at the right sub-array and go to step \(2\).Otherwise, set

`high = middle - 1`

to look at the left sub array and go to step \(2\).If

`low > high`

, return`-1`

to indicate that`item`

was not found.

## 15.2.2. Implementation#

To implement binary search, we need to write a function that takes in an array, size of the array and an item to search for. The function should return the index of the item if it is found in the array. If the item is not found, the function should return `-1`

. Download the following code `binary-search.c`

if you want to play with it.

**Code**

```
1#include <stdio.h>
2
3int binarySearch(int list[], int listLength, int item) {
4 int low = 0;
5 int high = listLength - 1;
6 int middle;
7
8 while (low <= high) {
9 middle = (low + high) / 2;
10 if (item == list[middle])
11 return middle;
12 else if (item < list[middle])
13 high = middle - 1;
14 else
15 low = middle + 1;
16 }
17 return -1;
18}
19
20int main() {
21 int list[] = {1, 3, 5, 7, 9, 10, 12};
22 printf("Found 9 at index %d\n", binarySearch(list, 7, 9));
23 return 0;
24}
```

**Output**

Found 9 at index 4

In line \(17\), we have exited from the while loop. This means that we have searched the entire array and have not found `item`

. Therefore, we return `-1`

to indicate that `item`

was not found.

## 15.2.3. Recursive Implementation#

We can also implement binary search recursively.

**Thinking recursively**, as we discussed in Section 11.2.1, requires us to think about a smaller problem. In the case of binary search, we can think about the smaller problem of searching a **smaller sub-array**. This would be our recursive case. Our **base/terminating case** is when we have searched the entire array and have or have not found `item`

.

How would we reduce the size of the array from one function call to the next recursive function call? We did a similar thing when we implemented isPalindrome function recursively inSection 11.3.2. The idea is to communicate with the next recursive function call the **new limits** of the array, *i.e.* the values of `low`

and `high`

.

Similarly, in our recursive binary search implementation below, we pass the values of `low`

and `high`

to the next recursive function call. We can do so by passing the values of `low`

and `high`

as arguments to the recursive function call.

**Code**

```
1int binarySearchHelper(int list[], int low, int high, int item) {
2 if (high < low) // failure - item not in list
3 return -1;
4
5 int middle = (low + high) / 2;
6 if (item == list[middle]) // success
7 return middle;
8
9 else if (item < list[middle]) // try bottom half
10 return binarySearchHelper(list, low, middle - 1, item);
11
12 else // try top half
13 return binarySearchHelper(list, middle + 1, high, item);
14}
```

In line \(1\), we pass the array `list`

, the values of `low`

and `high`

and the `item`

to search for as arguments to the recursive function call. Initially, we can call the function to set `low`

to `0`

and `high`

to the length of the array - 1.

Lines \(2\)–\(3\) handle the base case. If `high`

is less than `low`

, we have searched the entire array and have not found `item`

. Therefore, we return `-1`

to indicate that `item`

was not found.

Lines \(6\)–\(7\) handle another base case when we found `item`

in the array. If `item`

is equal to `list[middle]`

, we return `middle`

to indicate that we have found `item`

in the array.

Lines \(9\)–\(10\) handle the recursive case when `item`

is less than `list[middle]`

. In this case, we can discard the second half of the array by setting `high = middle - 1`

to the next recursive call. We can then call the recursive function to search the left sub-array by `binarySearchHelper(list, low, middle - 1, item)`

. The `return`

before the recursive function call is important. This ensures that the value returned by the recursive function call is returned by the function. You can drop the `return`

statement if it was a `void`

function, but since it should return an `int`

, we need to **return** the value returned by the recursive function call.

Lines \(12\)–\(13\) handle the recursive case when `item`

is greater than `list[middle]`

. In this case, we can discard the first half of the array by setting `low = middle + 1`

to the next recursive call. We can then call the recursive function to search the right sub-array by `binarySearchHelper(list, middle + 1, high, item)`

.

We can see that the values of `low`

and `high`

are updated in the recursive function call. This is how we reduce the size of the array from one function call to the next recursive function call.

**Reduce number of arguments** I would like to point out that functions with several arguments passed is not ideal, as someone may forget how to call the recursive function. We can improve this! We can implement a function that takes three arguments, an array, the size of the array and an item to search for. The function can then call the recursive function with the values of `low`

and `high`

set to `0`

and the length of the array - 1, respectively. This is what we do in the following implementation. Download the following code `binary-search-recursive.c`

if you want to play with it.

**Code**

```
1#include <stdio.h>
2
3int binarySearchHelper(int list[], int low, int high, int item);
4int binarySearchRecursive(int list[], int listLength, int item);
5
6int main(){
7 int list[] = {1, 3, 5, 7, 9, 10, 12};
8 printf("Found 9 in index %d", binarySearchRecursive(list, 7, 9));
9 return 0;
10}
11
12int binarySearchRecursive(int list[], int listLength, int item) {
13 return binarySearchHelper(list, 0, listLength - 1, item);
14}
15
16int binarySearchHelper(int list[], int low, int high, int item) {
17 if (high < low) // failure - item not in list
18 return -1;
19
20 int middle = (low + high) / 2;
21 if (item == list[middle]) // success
22 return middle;
23 else if (item < list[middle]) // try bottom half
24 return binarySearchHelper(list, low, middle - 1, item);
25 else // try top half
26 return binarySearchHelper(list, middle + 1, high, item);
27}
```

**Output**

Found 9 in index 4

In lines \(12\)–\(14\), we call the recursive function `binarySearchHelper`

with the values of `low`

and `high`

set to `0`

and the length of the array - 1, respectively. As a developer, you can later just sell this function to your users, and they can call it with just three arguments, an array, size of the array and an item to search for. The function will then call the recursive function with the values of `low`

and `high`

set to `0`

and the length of the array - 1, respectively.