C Program to search for an item using Binary Search
Last updated on September 23, 2020
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.
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.
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:
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:
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:
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:
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:
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:
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:
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:
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_2N\) or simply \(\log{}N\).
The above statement can be expressed in terms of Big-O notation as follows:
\[\mathcal{O}(\log{}n)\]
In plain English, \(\mathcal{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:
- C Program to sum the elements of an array
- C Program to find the count of even and odd elements in the array
- C Program to add two Matrices
- C Program to multiply two matrices
- C Program to find the transpose of a matrix
- C Program to search for an item using Linear Search
Load Comments