This article will teach you how the binary search sort works. In addition, there are working examples of binary Search in C++.
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)
Time complexity is the amount of time an algorithm requires to execute as a function of the length of the input.
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)
Below, we’ll go over the two distinct ways to implement the Binary Search 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.
l= Array (low or left) h= Array (high or right) m= mid
Convert the above description into 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
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);
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
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