C Program to search for an item using Binary Search

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:

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.

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.

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:

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:

60 > arr[4] => 60 > 50, so the search will proceed to the right portion of the array.

Step 2:

60 < arr[7] => 60 < 80, so the search will proceed to the left portion of the array.

Step 3:

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:

95 > arr[4] => 95 > 50, so the search will proceed to the right portion of the array.

Step 2:

95 > arr[7] => 95 > 80, so the search will proceed to the right portion of the array.

Step 3:

95 > arr[8] => 95 > 90, so the search will again proceed to the right portion of the array.

Step 4:

95 < arr[9] => 95 < 100, so the search will again proceed to the right portion of the array.

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 log2N or simply log N.

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

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:

Expected Output:

1st run:

2nd run:

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:

Leave a Comment

%d bloggers like this: