Linear Search allows us to search for a target item in an unsorted array.

However, if the array is sorted then we can use a much more efficient algorithm called Binary Search.

## Binary Search

In Binary search, we start by examining the target value with the element in the middle of the array. If the target value is equal to the middle element, our search was successful and we are done here. If the target value is not the same as the middle element and since the array is sorted, we can automatically remove half of the possible elements in the array.

If the target value is smaller than the middle element, then we can conclude that the target value must lie in the lower half of the array. Otherwise, the target value must lie in the upper half of the array.

Let’s say that the target value was smaller than the middle element, so we continue the search in the lower half of the array, again taking the target value and comparing it with the middle element. We keep repeating this process until the target value is found or there no more elements left to search.

Let’s take an example:

Suppose, we have an array `arr`

declared and initialized as:

1 2 |
#define SIZE 10 int arr[SIZE] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // sorted array |

To keep track of the index positions where we will search in the array, we need three additional variables: `low`

, `up`

and `midpoint`

.

The `low`

variable refers to the lower bound of the array. Initially, it will be set to `0`

.

1 |
low = 0 |

The `up`

variable refers to the upper bound of the array. Initially, it will be set to one less than the size of the array.

1 |
up = SIZE - 1 |

The `midpoint`

variable refers to the midpoint between the lower and upper bound of the array. The value of `midpoint`

will be calculated as follows:

1 |
midpoint = (low + up) / 2 |

If `target > arr[midpoint]`

, then we can conclude that the target value lies somewhere to the right of the middle element. To start searching in the right portion of the array, we update the value of `low`

to be `1`

greater than the `midpoint`

i.e `low = midpoint + 1`

. The value of upper bound (`up`

) is still the same, so we don’t need to change it.

If `target < arr[midpoint]`

, then we can conclude that the target value lies somewhere to the left of the middle element. To start searching in the left portion of the array, we update the value of `up`

to be `1`

less than the `midpoint`

i.e `up = midpoint - 1`

. The value of lower bound (`low`

) is still the same, so we don’t need to change it.

If `target == arr[midpoint]`

, the target value is found and our search was successful.

If `low > up`

, then the target value is not found as there are no more elements left to search.

The following are the steps to search for the target value `60`

inside the sorted array.

**Step 1**:

1 |
low = 0, up = 9,midpoint = 4 |

`60 > arr[4] => 60 > 50`

, so the search will proceed to the right portion of the array.

1 2 |
low = midpoint + 1 => low = 5 midpoint = (low + up) / 2 => m = (5 + 9) / 2 => m = 7 |

**Step 2**:

1 |
low = 5, up = 9, midpoint = 7 |

`60 < arr[7] => 60 < 80`

, so the search will proceed to the left portion of the array.

1 2 |
up = midpoint - 1 => 6 midpoint = (5 + 6) / 2 => m = 5 |

**Step 3**:

1 |
low = 5, up = 6, midpoint = 5 |

`60 == arr[5] => 60 == 60`

, the target value found. Our search was successful.

Note that we have found the target value in 3 steps. The same search using Linear search algorithm would take 6 steps.

Now, let’s see what would happen if the target value is not found inside the array.

The following are the steps to search for the target value `95`

inside the sorted array.

**Step 1**:

1 |
low = 0, up = 9, midpoint = 4 |

`95 > arr[4] => 95 > 50`

, so the search will proceed to the right portion of the array.

1 2 |
low = midpoint + 1 => low = 5 midpoint = (low + up) / 2 => midpoint = (5 + 9) / 2 => midpoint = 7 |

**Step 2**:

1 |
low = 5, up = 9, midpoint = 7 |

`95 > arr[7] => 95 > 80`

, so the search will proceed to the right portion of the array.

1 2 |
low = midpoint + 1 => 8 midpoint = (8 + 9) / 2 => midpoint = 8 |

**Step 3**:

1 |
low = 8, up = 9, midpoint = 8 |

`95 > arr[8] => 95 > 90`

, so the search will again proceed to the right portion of the array.

1 2 |
low = midpoint + 1 => 9 midpoint = (9 + 9) / 2 => midpoint = 9 |

**Step 4**:

1 |
low = 9, up = 9, midpoint = 9 |

`95 < arr[9] => 95 < 100`

, so the search will again proceed to the right portion of the array.

1 2 |
up = midpoint - 1 => 8 midpoint = (10 + 9) / 2 => midpoint = 8 |

Note that for the first time, the value of `low`

(`9`

) is greater than the value of `up`

(`8`

). Hence, our target value is not present in the array.

## Time complexity

Let’s now examine the efficiency of Binary search in term of Big O Notation.

If the size of the array is `3`

, then the maximum number of steps it would take to find the target value is 2.

Similarly, If the size of the array is `8`

, then the maximum number of steps it would take to find the target value is 3.

The following table lists the size of the array and the maximum number of steps it would take to find the target value.

Size | Steps |
---|---|

3 | 2 |

8 | 3 |

16 | 4 |

32 | 5 |

64 | 6 |

In general, we can say that with an array of size `N`

, the maximum number of steps it would take to find the target value is `log`

or simply _{2}N`log N`

.

The above statement can be expressed in terms of Big-O notation as follows:

1 |
O(log N) |

In plain English, `O(log N)`

simply means that for `N`

number of elements, an algorithm would take `Log N`

number of steps

## Binary Search C Program

The following is a C program to search for the target using Binary search algorithm:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
/***************************************************** Program to search for an item using binary search *****************************************************/ #include <stdio.h> #define SIZE 10 int binary_search(int arr[], int target); // function declaration int main() { int arr[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // sorted array int target; // number to be searched int index; // index position of the target printf("Enter number to search: "); scanf("%d", &target); index = binary_search(arr, target); if(index != -1) { printf("Item %d found at index %d.", target, index); } else { printf("Item %d not found.", target); } return 0; } /* * binary_search() returns index position of the * target item. Returns -1, if the target item is not found. */ int binary_search(int arr[], int target) { /* variables to keep track of the index positions where we will search in the array */ int low = 0, up = SIZE - 1, midpoint; while(low <= up) { midpoint = (low + up) / 2; // calculate midpoint if(target > arr[midpoint]) { // proceed search to the right portion low = midpoint + 1; } else if(target < arr[midpoint]) { // proceed search to the left portion up = midpoint - 1; } else if(target == arr[midpoint]) { // target value found. Return the index and exit the function return midpoint; } } // target value not found, return -1 and exit the function return -1; } |

**Expected Output:**

1st run:

1 2 |
Enter number to search: 5 Item 5 found at index 4. |

2nd run:

1 2 |
Enter number to search: 101 Item 101 not found. |

## How it works

The meat of the program lies in the `binary_search()`

function.

The `binary_search()`

function takes an array and target value as arguments, and returns the index position of the target value. If the target value is not found `-1`

is returned.

In line 45, we are declaring variables to keep track of the index positions where we will search in the array.

In lines 47-68, we have a while loop which runs until the value of lower bound (`low`

) is smaller than or equal to the value of upper bound (`up`

).

In lines 51-67, we have an if-else statement which compares the target value with the middle element and updates the value of low bound (`low`

) and upper bound (`up`

) accordingly. In case, the target value is equal to the middle element, we return the index position of the middle element and exit the function.

When the loop terminates, we return a value of `-1`

to indicate that the target value is not present in the array.

**Recommended Reading:**