Home »
Algorithms
Binary Search: Algorithm, Example & C, C++ Implementations
Binary Search Algorithm: In this tutorial, we will learn about the binary search algorithm, and it's time complexity in detail and then, implemented it in both C & C++. As a follow up there are several use cases or variations of binary search.
By Radib Kar Last updated : August 14, 2023
Binary Search Algorithm
The word binary means two. Thus it's evident that the algorithm must have some sort of connection with 2. Binary search is one of the most popular algorithms which searches a key from a sorted range in logarithmic time complexity. First, we need a sorted range for the binary search to work. Binary search can't work on any unsorted range. The idea behind the binary search ctually relies on this "sorted" word.
Binary Search Example
Let's take an example to describe the binary search:
Input range: [ 12, 14 , 18, 22, 45, 67, 99, 107] , key to be searched= 67
The basic steps behind the binary search is to first divide the range into two(that's why binary) half based on a pivot. How will we choose the pivot?
We will pick the mid element as our pivot. To find the mid element simple do mid=(left+right)/2 where left is the start index of the current range and right is end index of the current range.
Now we need to check whether the search key is the same as the pivot element or not. If it's the same then, we are done. We found the key.
If it's not the same then there can be two cases:
- key> pivot element:
In this case, we need to check only the right half of the range. Right half means the elements which are greater than the pivot. This is possible only because the array is sorted. Since the array is sorted it's guaranteed that search key will not appear in the left half as it's greater than the pivot. So we can discard the left half and shrink our range to [pivot index+1, right] for further search.
- key< pivot element:
In this case, we need to check only the left half of the range. Left half means the elements which are less than the pivot. This is possible only because the array is sorted. Since the array is sorted it's guaranteed that search key will not appear in the right half as it's less than the pivot. So we can discard the right half and shrink our range to [left, pivot index-1] for further search.
Steps for Binary Search Algorithm
So every time,
- We will find the pivot index=(left+ right)/2.
- We will check whether the pivot element is key or not, if it's the key then terminate as the key is found. Otherwise, shrink the range and update left or right as per choices discussed above.
- Continue until range collapse down to 0(left>right).
Below is the dry run with the algorithm:
Iteration 1:
Initially the range is [ 12, 14 , 18, 22, 45, 67, 99, 107], key=67
So left=0, right= 7
Pivot index is (0+7)/2=3, so pivot is 22
Now pivot < 67(key)
So we need to search the right half only, hence left=pivot index+1=4
Thus the searching range now: [45, 67, 99 , 107]
Iteration 2:
Now, the range is [45, 67, 99, 107], key=67
So left=4, right= 7
Pivot index is (4+7)/2=5, so pivot is 67
Now pivot == 67(key) so key is found
Terminate the search and return pivot index
Lets' now check how the algo terminates if key is not there:
---------------------------------
Say the key is now 70
Below is the dry run with the algorithm:
Iteration 1:
Initially the range is [ 12, 14 , 18, 22, 45, 67, 99, 107], key=70
So left=0, right= 7
Pivot index is (0+7)/2=3, so pivot is 22
Now pivot < 70(key)
So we need to search the right half only, hence left=pivot index+1=4
Thus the searching range now: [45, 67, 99 , 107]
Iteration 2:
Now, the range is [45, 67, 99, 107], key=70
So left=4, right= 7
Pivot index is (4+7)/2=5, so pivot is 70
Now pivot < 70 (key)
So we need to search in the right half only, hence left=pivot index+1=6
Thus the range will be : [99, 107]
Iteration 3:
Now, the range is [99, 107], key=70
So left=6, right= 7
Pivot index is (6+7)/2=6, so pivot is 99
Now pivot > 70 (key)
So we need to search in the left half only, hence right=pivot index-1=6
Thus the range will be undefined as left=6
but right is now 5, thus search terminates here.
Key not found.
Time complexity
The time complexity of the binary search is of course logarithmic, O(log2n). This is because every time our search range becomes half
So, T(n)=T(n/2)+1 (time for finding pivot)
Using the master theorem you can find T(n) to be Log2n. Also, you can think this as a series of n/2+n/4+n/8+n/16+….+1 which is Log2(n).
Better way to find the pivot index
We were finding the pivot index like (left+ right)/2. But one thing to notice that (left+ right) has a chance to lead to integer overflow. Hence a better method is to find the pivot index like below:
Pivot index= left+ (right-left)/2
Binary Search Implementation in C (Iterative Implementation)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
//iterative binary search
int binary_search_iterative(int* arr, int key, int n)
{
int left = 0, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main()
{
int n = 8000000;
int* arr = (int*)(malloc(sizeof(int) * n));
for (int i = 0; i < n; i++)
arr[i] = i + 1;
//key there
int key = 3115999;
clock_t tStart1 = clock();
int index = binary_search_iterative(arr, key, n);
if (index == -1)
printf("key not found\n");
else
printf("%d found at index(0 based): %d\n", key, index);
clock_t tend1 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
//key not there
key = 8000001;
clock_t tStart2 = clock();
index = binary_search_iterative(arr, key, n);
if (index == -1)
printf("key not found\n");
else
printf("%d found at index(0 based): %d\n", key, index);
clock_t tend2 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);
return 0;
}
Output:
3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.000080s
key not found
Time taken in recursive binary search: 0.000011s
Binary Search Implementation in C++ (Iterative Implementation)
#include <bits/stdc++.h>
using namespace std;
//iterative binary search
int binary_search_iterative(vector<int> arr, int key)
{
int left = 0, right = arr.size();
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main()
{
int n = 8000000;
vector<int> arr(n);
for (int i = 0; i < n; i++)
arr[i] = i + 1;
//key there
int key = 3115999;
clock_t tStart1 = clock();
int index = binary_search_iterative(arr, key);
if (index == -1)
cout << key << " not found\n";
else
cout << key << " found at index(0 based): " << index << endl;
clock_t tend1 = clock();
printf("Time taken in iterative binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
//key not there
key = 8000001;
clock_t tStart2 = clock();
index = binary_search_iterative(arr, key);
if (index == -1)
cout << key << " not found\n";
else
cout << key << " found at index(0 based): " << index << endl;
clock_t tend2 = clock();
printf("Time taken in iterative binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);
return 0;
}
Output:
3115999 found at index(0 based): 3115998
Time taken in iterative binary search: 0.034050s
8000001 not found
Time taken in iterative binary search: 0.031010s
Binary Search Implementation in C (Recursive Implementation)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
//recursive binary search
int binary_search_recursive(int* arr, int key, int left, int right)
{
if (left > right)
return -1;
srand(time(NULL));
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key) //right half
return binary_search_recursive(arr, key, mid + 1, right);
//else left half
return binary_search_recursive(arr, key, left, mid - 1);
}
int main()
{
int n = 8000000;
int* arr = (int*)(malloc(sizeof(int) * n));
for (int i = 0; i < n; i++)
arr[i] = i + 1;
//key there
int key = 3115999;
clock_t tStart1 = clock();
int index = binary_search_recursive(arr, key, 0, n);
if (index == -1)
printf("key not found\n");
else
printf("%d found at index(0 based): %d\n", key, index);
clock_t tend1 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
//key not there
key = 8000001;
clock_t tStart2 = clock();
index = binary_search_recursive(arr, key, 0, n);
if (index == -1)
printf("key not found\n");
else
printf("%d found at index(0 based): %d\n", key, index);
clock_t tend2 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);
return 0;
}
Output:
3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.000121s
key not found
Time taken in recursive binary search: 0.000063s
Binary Search Implementation in C++ (Recursive Implementation)
#include <bits/stdc++.h>
using namespace std;
//recursive binary search
int binary_search_recursive(vector<int> arr, int key, int left, int right)
{
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key) //right half
return binary_search_recursive(arr, key, mid + 1, right);
//else left half
return binary_search_recursive(arr, key, left, mid - 1);
}
int main()
{
int n = 8000000;
vector<int> arr(n);
for (int i = 0; i < n; i++)
arr[i] = i + 1;
//key there
int key = 3115999;
clock_t tStart1 = clock();
int index = binary_search_recursive(arr, key, 0, n);
if (index == -1)
cout << key << " not found\n";
else
cout << key << " found at index(0 based): " << index << endl;
clock_t tend1 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
//key not there
key = 8000001;
clock_t tStart2 = clock();
index = binary_search_recursive(arr, key, 0, n);
if (index == -1)
cout << key << " not found\n";
else
cout << key << " found at index(0 based): " << index << endl;
clock_t tend2 = clock();
printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);
return 0;
}
Output:
3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.634202s
8000001 not found
Time taken in recursive binary search: 0.705844s
Variation of binary Search
Binary search has a lot of variation which still sticks to the main idea and time complexity, but there are some modifications.
- Meta binary search or One-sided Binary search
- Randomized binary search