Introduction to Binary Search with C++

This article will teach you how the binary search sort works. In addition, there are working examples of binary Search in C++.

What is Binary Search?

By repeatedly halving the search interval, binary Search is a searching algorithm utilized in a sorted array. Utilizing the knowledge that an array is sorted; a binary search reduces the time complexity to O(Log N)

Binary Search: Time Complexities

Time complexity is the amount of time an algorithm requires to execute as a function of the length of the input.

Binary Search: Space Complexities

The “space complexity” is the total memory space an algorithm or program uses, including the space needed for input values while the program is running. You can Determine how space-intensive an algorithm is by figuring out how much space its variables take up.

space complexity = O(1)

Binary Search: why use it?

• The binary search algorithm is popular and widely used in C++ and other programming languages. It can quickly identify items within sorted arrays or collections, making it a time-saving tool for large data sets.
• The Binary Search is more complex than a linear search through an array or collection, which makes it useful in a wider range of situations.
• You don’t have to compare things in a straight line to find the index you want. You can instead use middle points and the divide-and-conquer method to narrow down the choices for each comparison.
• Also, runtime performance improves as the data set grows. It is because binary searches take logarithmic time, which makes them faster and more reliable when accessing larger data sets. So, when working with large datasets in C++ programming, a binary search algorithm can be constructive.
• For fast and reliable results in modern software development, it is important to consider space and time complexity when choosing a search algorithm like binary Search. It’s important to consider space and time complexity when choosing a search algorithm, like a binary search. If you select an inefficient method, it may use more memory and take longer to run, which is usually bad for applications that need the best performance. Binary Search can be much better than linear Search when searching through large datasets because it takes advantage of the data structure’s sorted order and reduces the number of comparisons needed to find an element. Binary Search also has a time complexity of O(log n), which is much more efficient than linear search algorithms that carry out O(n) comparisons.

Binary Search: Approaches

Below, we’ll go over the two distinct ways to implement the Binary Search Algorithm.

Binary Search: General Procedure to practice algorithm

1 – The general procedures for both approaches are outlined below.

An ordered array is given below.

Consider a = 16 to be the search element.

2 – The low and high pointers are placed in the lowest and highest positions, respectively.

Low =11

High = 17

3 – Determine the element in the middle of an array.

array[(low + high)/2]

array [(11+17)/2]=14

4 – If a is equal to mid, return mid;

Otherwise, compare the element to be searched with m.

Here 16 is different from mid, so we keep searching.

5 – If a is greater than mid, Compare ‘a’ with the middle element of the elements to the right of mid. This is achieved by setting:

Low -> low = mid + 1

Low = 14 + 1

6 – Else, compare ‘a’ with the middle element of the elements to the left side of mid. This is achieved by configuring:

high -> high = mid – 1,

high = 14 – 1

7 – Here, the number we are looking for is 16, which is greater than mid, so we will go to the right side of mid and follow step 5.

Low = 14 + 1.

Our low is 15 now.

Low =15 High = 17

8 – Repeat steps 3 through 6 until low and high meet.

array [(15+17)/2] =16

16 found.

Binary Search: pseudocode

l= Array (low or left)
h= Array (high or right)
m= mid

Convert the above description into pseudocode:

Iterative pseudocode

while l <= h
m = l + (h - l) / 2;
if array(m) == element
return m;
if array[m] < element
l = m + 1;
else
h = m - 1;
return l

Recursive pseudocode

if h >= l
int m = l + (h - l) / 2;
if array[m] == element
return m;
if array[m] > element
//element is on the left side
return binarySearch(array, element, l, m - 1);
//element is on the right side

return binarySearch(array, element, m + 1, h);

Binary Search: Iteration Method

The binary search method starts by splitting the array in half and then figuring out which half has the element being looked for. From there, it divides the array repeatedly until the element is found or it does not exist. With each iteration, the binary Search iterative method reduces the area in which to look for the target, accelerating its success in finding it quickly. It is beneficial for searching through large data sets because it takes much less time than linear search methods.

Example Code

#include <iostream>

using namespace std;

bool binarySearch(int array[], int element, int l, int h) {
// Loop keeps looking for the element in the array based on the Iterative Method
while (l <= h) {
//To search the mid element of the array
int m = l + (h - l) / 2;

if (array[m] == element)
return m;

if (array[m] < element)
l = m + 1;

else
h = m - 1;
}
return 0;
}

int main(void) {
//The search array is:
int array[] = {
11,
12,
13,
14,
15,
16,
17
};
//The Element needs to be Search
int element;
cout << "Enter the number to search:";
cin >> element;
//Size of the array
int size = sizeof(array) / sizeof(array[0]);

bool elementFound = binarySearch(array, element, 0, size - 1);

if (elementFound)

printf("Element Found");
else

printf("No Element Found");

}

Output

Enter the number to search: 12
Element Found

Binary Search: Recursive Method

The recursive method of binary Search is better than the standard method because it is more scalable. By making recursive calls, multiple chunks can be searched at the same time, and this makes the processing go much quicker than it would with a linear approach.

Example Code

#include <iostream>

using namespace std;

int binarySearch(int array[], int element, int l, int h) {
if (h >= l) {
int m = l + (h - l) / 2;

// If found at m, then return it
if (array[m] == element)
return m;

// Keep looking for the element in array on left half
if (array[m] > element)
return binarySearch(array, element, l, m - 1);

// Keep looking for the element in array on right half
return binarySearch(array, element, m + 1, h);
}

return -1;
}

int main(void) {
//The search array is:
int array[] = {
11,
12,
13,
14,
15,
16,
17
};
//The Element needs to be Search
int element;
cout << "Enter the number to search:";
cin >> element;
//Size of the array
int size = sizeof(array) / sizeof(array[0]);

bool elementFound = binarySearch(array, element, 0, size - 1);

if (elementFound == 1)

printf("Element Found");
else

printf("No Element Found");
}

Output

Enter the number to search:17
Element Found