# 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(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.

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!