Binary Search in C++

Binary Search in C++

2 mins read2.4K Views Comment
Updated on Jan 16, 2023 16:33 IST

This article is talking about binary search in iterative and recursive way using C++.

2022_08_MicrosoftTeams-image-9.jpg

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:

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:

Top C++ Interview Questions and Answers for 2024
Top C++ Interview Questions and Answers for 2024
C++ is a popular object-oriented programming (OOP) language. Due to its reliability, speed, compatibility, and performance, it is widely used in the development of operating systems, applications, games, servers, and...read more
C++ if else Statement
C++ if else Statement
In this article, we will learn how decision-making is done in C++ by using conditional statements. These statements work on the logic that a block of code will be executed...read more
Understanding Break Statement in C++
Understanding Break Statement in C++
The break statement is loop control statement that is used for the terminating the loop. These are used in the situations where we do not have the idea about actual...read more

Also explore: Friend function in C++

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:

2022_08_image-94.jpg

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.

2022_08_image-95.jpg

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:

2022_08_image-96.jpg

Now, as x<mid, i.e., 3 < 5, we will set high = mid-1 = 4, as shown below:

2022_08_image-97.jpg

Step 2 is repeated until high meets low:

2022_08_image-101.jpg
2022_08_image-100.jpg

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);
}
Copy code

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);
}
Copy code

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++.

About the Author

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