Binary Search in C++
This article is talking about binary search in iterative and recursive way using C++.
In this article, we will understand how to perform binary search in C++. This mechanism is used to find a particular element from the sorted array by continuously halving the array and searching for the specified element in the half array(s). The process repeats till a match is found.
We will be covering the following sections today:
- What is Binary Search?
- Working of Binary Search
- Binary Search in C++ using Iterative Method
- Binary Search in C++ using Recursive Method
- Binary Search Complexity
What is Binary Search?
Finding an element’s location in a sorted array in C++ is done using the searching method known as binary Search. This approach can only be applied to a sorted data structure. So, if the elements are not already sorted, they must be sorted first.
This algorithm constantly searches for the specified element from the middle portion of the sorted array.
Let’s understand the working of this algorithm in detail below:
Also explore: Friend function in C++
Best-suited C++ courses for you
Learn C++ with these high-rated online courses
Working of Binary Search
Binary Search can be implemented in two ways:
- Iterative Method
- Recursive Method
The general working of both methods is discussed below.
Let’s say we have the following sorted array:
Suppose we are searching for the element x=3.
Step 1:
Set two pointers – low and high, at the lowest and the highest positions, respectively.
Step 2:
Now, find the middle element mid of the array using the following formula:
arr[(low + high)/2]
If x==mid, return the value of mid. Otherwise, compare the element x with mid.
If x exceeds mid, i.e., x>mid, x is compared to the midle element of the elements on the right of the mid. To execute this, set low to low=mid+1.
If x<mid, x has to be compared to the middle element of the elements on the left of the mid. To execute this, set high to high=mid-1.
We get mid = 6, as shown:
Now, as x<mid, i.e., 3 < 5, we will set high = mid-1 = 4, as shown below:
Step 2 is repeated until high meets low:
Thus, we have found the position of x=4 in the sorted array.
Binary search using the iterative method
Now, let’s see how we implement this logic in C++ using iterative method://Binary Search in C++ using iterative method
#include <iostream>using namespace std;
int binarySearch(int array[], int x, int low, int high) { // Repeat until the pointers low and high meet each other while (low <= high) { int mid = low + (high - low) / 2;
if (array[mid] == x) return mid;
if (array[mid] < x) low = mid + 1;
else high = mid - 1; }
return -1;}
int main(void) { int array[] = {2, 3, 4, 5, 6, 7, 8}; int x = 3; int n = sizeof(array) / sizeof(array[0]); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result);}
Output:
Element is found at index 1
Binary search using recursive method
Next, let’s see how we perform binary search in C++ using recursive method: // Binary Search in C++ using recursive method
#include <iostream>using namespace std;
int binarySearch(int array[], int x, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2;
// If found at mid, then return it if (array[mid] == x) return mid;
// Search the left half if (array[mid] > x) return binarySearch(array, x, low, mid - 1);
// Search the right half return binarySearch(array, x, mid + 1, high); }
return -1;}
int main(void) { int array[] = {2, 3, 4, 5, 6, 7, 8}; int x = 3; int n = sizeof(array) / sizeof(array[0]); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result);}
Output
Element is found at index 1
Binary Search Complexity
| Best Case Time Complexity | O(1) |
| Worst Case Time Complexity | O(log n) |
| Average Time Complexity | O(log n) |
| Space Complexity | O(1) |
Endnotes
I hope this post gave you a good idea of how C++ implements binary Search. This is a popular technique to find the position of a given element in a sorted array or list. We discussed the two ways we can perform binary Search – iterative and recursive. Both methods work on the same logic with a few code alterations. You can check out our other articles if you’re interested in learning C++.
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
