# Binary Search in C, C++

**Binary search** is one of the most popular algorithms which searches a key from a sorted range in logarithmic time complexity. In this article, we have discussed the algorithm, it's time complexity in detail and them, implemented in both C & C++. As a follow up there are several use cases or variations of binary search.

Submitted by Radib Kar, on July 20, 2020

## Binary search

The word **binary** means two. Thus it's evident that the algorithm must have some sort of connection with 2. What's that?

Okay first of all 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 actually relies on this "sorted" word.

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.

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(log _{2}n)*. 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 *Log _{2}n*. Also, you can think this as a series of

*n/2+n/4+n/8+n/16+….+1*which is

*Log*.

_{2}(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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions