Binary Search in C++

# Binary Search in C++

Updated on Jan 16, 2023 16:33 IST

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

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

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