Welcome to programmopedia! This article’s topic is going to be the searching of arrays again but this time we are going to search array using binary search algorithm in c++. We have already discussed a basic linear search algorithm but that was not time efficient. Binary search makes searching fast and time-efficient as it doesn’t search the whole array to find a match. Rather it splits the array based on some conditions. It can be applied to other data structures also. Let’s first understand, how the binary search algorithm in c++ works.
What is Binary search algorithm?
Binary search is a searching algorithm that uses divide and conquer approach to make searching efficient. To apply binary search on any data structure including arrays, the data must be sorted in an order. Binary search can not be applied to unsorted data set. Now see the working of binary search stepwise.
- The first and the core step is to divide the complete array into 2 half portions. We can refer to the first as left and the second as the right half.
- Now if n is greater than the midpoint, start searching the right half of the array. The left half will be eliminated from our search space.
- But if n is smaller than the midpoint, search the left half of the array. We will eliminate the right half from our search space.
- Keep on repeating the binary search until n is equal to the midpoint. That’s the point where we will stop searching further.
- In binary search, half of the search space is eliminated on every iteration which makes this algorithm efficient. The same thing is illustrated in the below diagram.
To implement this concept in a programming language, we need three variables “start”, “mid”, and “end” as shown in the above picture. Now let’s see how to implement the binary search algorithm in c++.
How to implement binary search algorithm in c++?
- Declare an array of integers and some variables like
"start","end","mid","size", and"n". -
"Start","end"and"mid"will be used to keep track of the starting index, middle index, and ending index of the array portion under binary search. - The
"size"will be used to define array size and"n"is a number to search in the array. - Ask the user to enter the array size and read input in the array from the user.
//Declaring variables
int Arr[50];
int n;
int start;
int end;
int mid;
int size;
cout << "Enter array size" << endl;
cin >> size;
//read array element from user
for (int i = 0; i < size; i++) {
cout << "Enter 10 Elements element at index " << i << " :";
cin >> Arr[i];
}
- Sort the data first s because binary search requires sorted data to work efficiently.
- Print the sorted array to the user to let him choose a number to search.
- Ask the user to enter a number to search and read input in
"n".
//sort the array in ascending order
int temp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (Arr[i] > Arr[j]) {
temp = Arr[j];
Arr[j] = Arr[i];
Arr[i] = temp;
}
}
}
// printing the sorted array
for (int i = 0; i < size; i++) {
cout << Arr[i] << " ";
}
- Initialize
"start"to 0,"end"to"size - 1"and calculate mid point to initialize"mid". - Now execute a while loop until
"start"is less than"end". While loop will terminate If the"start"becomes greater than"end". It indicates no match in the array. - Now inside the while loop, we need three important conditions.
- If n is greater than the midpoint of the array, set the
"start"variable to one greater than"mid". In this way, we will eliminate the left half portion of the array from search space. - But if
nis smaller than the midpoint, set"start"to one less than the"mid"variable. So, this time we will eliminate the right half portion of the array from search space. - After the elimination, we will get a new array space. Calculate the midpoint of this new array.
- Print a success message along with
"mid"value if n is equal to the midpoint of the array.
//search n in the array using binary search
cout << "Enter Element to be Search: ";
cin >> n;
start = 0;
end = size - 1;
mid = (start + end) / 2;
while (start <= end) {
if (n > Arr[mid]) {
start = mid + 1;
} else if (n == Arr[mid]) {
cout << n << " found at Index " << mid << endl;
break;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
- After the completion of the loop, if “start” is greater than “end”, print the not found message.
if (start > end) {
cout << "Sorry! number " << n << " not found" << endl;
}
Simple binary search program in c++:
Now see the complete code of all the steps at once to better understand the concept.
#include<iostream>
using namespace std;
int main() {
//Declaring variables
int Arr[50];
int n;
int start;
int end;
int mid;
int size;
cout << "Enter array size" << endl;
cin >> size;
cout << endl;
//read array element from user
for (int i = 0; i < size; i++) {
cout << "Enter 10 Elements element at index " << i << " :";
cin >> Arr[i];
}
//sort the array in ascending order
int temp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (Arr[i] > Arr[j]) {
//swapping with smallest element of array.
temp = Arr[j];
Arr[j] = Arr[i];
Arr[i] = temp;
}
}
}
// printing the sorted array
cout << endl;
for (int i = 0; i < size; i++) {
cout << Arr[i] << " ";
}
cout << endl;
//search n in the array using binary search
cout << "Enter Element to be Search: ";
cin >> n;
start = 0;
end = size - 1;
mid = (start + end) / 2;
while (start <= end) {
if (n > Arr[mid]) {
start = mid + 1;
} else if (n == Arr[mid]) {
cout << n << " found at Index " << mid << endl;
break;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
if (start > end) {
cout << "Sorry! number " << n << " not found" << endl;
}
cout << endl;
return 0;
}
Output of program:
Binary search program using function:
This program does the same thing but it’s built with a bit different approach. This time we have written a function to apply binary search algorithm in c++ and search n in the array. Let’s discuss the changes in the code stepwise.
- We have written a function called
"SearchArray"which takes an array, array size, and n as parameters. - All the steps and conditions of binary search are implemented inside a while loop.
- Once the
"mid"becomes equal ton, set the result to mid. - If
"start"becomes greater than"end", set the result to"-1". - Return result at the end of the function.
int SearchArray(int Arr[], int size, int n) {
int start = 0;
int end = size - 1;
int mid = (start + end) / 2;
int result = 0;
while (start <= end) {
if (n > Arr[mid]) {
start = mid + 1;
} else if (n == Arr[mid]) {
result = mid;
break;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
if (start > end) {
result = -1;
}
return result;
}
- Then inside the main, print the index with a success message if “-1” is not returned by the function.
//search n in the array using binary search
cout << "Enter Element to be Search: ";
cin >> n;
int result = SearchArray(Arr, size, n);
if (result == -1) {
cout << n << " not found in array" << endl;
} else {
cout << n << " found at index " << result << endl;
}
That’s how we can implement binary search using a function in c++. Let’s see the complete program code now.
#include<iostream>
using namespace std;
int SearchArray(int Arr[], int size, int n) {
int start = 0;
int end = size - 1;
int mid = (start + end) / 2;
int result = 0;
while (start <= end) {
if (n > Arr[mid]) {
start = mid + 1;
} else if (n == Arr[mid]) {
result = mid;
break;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
if (start > end) {
result = -1;
}
return result;
}
int main() {
//Declaring variables
int Arr[50];
int n;
int size;
cout << "Enter array size" << endl;
cin >> size;
cout << endl;
//read array element from user
for (int i = 0; i < size; i++) {
cout << "Enter 10 Elements element at index " << i << " :";
cin >> Arr[i];
}
//sort the array in ascending order
int temp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (Arr[i] > Arr[j]) {
temp = Arr[j];
Arr[j] = Arr[i];
Arr[i] = temp;
}
}
}
// printing the sorted array
for (int i = 0; i < size; i++) {
cout << Arr[i] << " ";
}
cout << endl;
//search n in the array using binary search
cout << "Enter Element to be Search: ";
cin >> n;
int result = SearchArray(Arr, size, n);
if (result == -1) {
cout << n << " not found in array" << endl;
} else {
cout << n << " found at index " << result << endl;
}
return 0;
}
Output of program:
Binary search program using recursion:
This is another variation of the binary search program in c++. This time we are using the recursive approach to implement a binary search algorithm. Let’s discuss how it’s different from the above two programs.
- This time the
"SearchArray"function takes"start"and"end"as parameters also. - If n becomes equal to
"mid", we return"mid"as an index. - If
nis greater than mid, we call the same"SearchArray"function inside its body but with"mid+1"instead of"start"as an argument to eliminate the left array portion. - In the same way, pass
"mid-1"instead of"end"to eliminate the right half if n is less than"mid". - If
"start"gets greater than"end", return “-1” means n not found.
int SearchArray(int Arr[], int start, int end, int n) {
int mid;
mid = (start + end) / 2;
if (start > end) {
return 0;
} else if (Arr[mid] == n) {
return (mid);
} else if (Arr[mid] > n) {
SearchArray(Arr, start, mid - 1, n);
} else if (Arr[mid] < n) {
SearchArray(Arr, mid + 1, end, n);
}
}
This recursive function will apply binary search on the array. Now see the complete of c++ program to implement binary search algorithm using recursion.
#include<iostream>
using namespace std;
int SearchArray(int Arr[], int start, int end, int n) {
int mid;
mid = (start + end) / 2;
if (start > end) {
return 0;
} else if (Arr[mid] == n) {
return (mid);
} else if (Arr[mid] > n) {
SearchArray(Arr, start, mid - 1, n);
} else if (Arr[mid] < n) {
SearchArray(Arr, mid + 1, end, n);
}
}
int main() {
int Arr[50];
int n;
int size;
cout << "Enter array size" << endl;
cin >> size;
int start = 0;
int end = size - 1;
cout << endl;
//read array element from user
for (int i = 0; i < size; i++) {
cout << "Enter 10 Elements element at index " << i << " :";
cin >> Arr[i];
}
//sort the array in ascending order
int temp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (Arr[i] > Arr[j]) {
temp = Arr[j];
Arr[j] = Arr[i];
Arr[i] = temp;
}
}
}
// printing the sorted array
for (int i = 0; i < size; i++) {
cout << Arr[i] << " ";
}
cout << endl;
//search n in the array using binary search
cout << "Enter Element to be Search: ";
cin >> n;
int result = SearchArray(Arr, start, end, n);
if (result == -1) {
cout << n << " not found in array" << endl;
} else {
cout << n << " found at index " << result << endl;
}
return 0;
}
Output of program:
Now I am going to conclude this article. We have discussed every aspect of the binary search algorithm in c++. We also implemented different variations of the algorithm in c++. Now I think the concept of binary search is crystal clear to all my readers. I hope you liked my effort and the shared information. Thanks for reading and supporting us.