Last Updated on May 17, 2023 by Prepbytes
A common approach for finding a specific element in a sorted list of elements is a binary search. In order to find the target element or when the search interval is empty, the search interval is divided repeatedly in half, with the non-target half being eliminated. The binary search method in C++ and how to use it to locate a specific element in an array are both covered in this article along with sample code. These are the techniques:
- Simple binary search program
- Allow user to define array size and sorts before searching
- Using user-defined function
- Using recursion
Before executing the aforementioned program, if you are not familiar with the binary search strategy, you may look up a binary search to understand more about its logic and algorithm.
What is Binary Search in C++?
In C++ programming, before entering the element or number to be searched, you must first ask the user to submit any items for the array. The binary search approach refers to this.
The element’s location will be displayed if the element is located in the list using the binary search method and is there. The following C++ program asks the user to enter up to 10 array elements and a search element. This program does a simple binary search.
Code Implementation of Binary Search in C++
#include<iostream>
using namespace std;
int main()
{
int i, arr[10], num, first, last, middle;
cout<<"Enter 10 Elements (in ascending order): ";
for(i=0; i<10; i++)
cin>>arr[i];
cout<<"\nEnter Element to be Search: ";
cin>>num;
first = 0;
last = 9;
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
{
cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
break;
}
else
last = middle-1;
middle = (first+last)/2;
}
if(first>last)
cout<<"\nThe number, "<<num<<" is not found in given Array";
cout<<endl;
return 0;
}
Input:
2 3 5 6 8 9 10 15 16 25 89 110
89Output:
Enter 10 Elements (in ascending order):
Enter Element to be Search:
The number, 89 is not found in given ArrayAlgorithm of Binary Search in C++
- Declare the variables, then enter an array’s elements in any order (ascending or descending).
- The array element listings should be split in half.
- Now compare the target elements with the array’s middle element. Additionally, if the middle element’s value matches the target element’s value, return the middle element’s location and the search is finished.
- We search the elements in the lower half of an array if the target element is less than the middle element.
- We must seek the target element in the bigger half of the array if it is larger than the middle element.
- Up until the requested element is not present in the sorted array, steps 4, 5, and 6 will be repeatedly performed.
Explanation of Binary Search in C++:
- If a user types in 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the element to be searched is element number 8, the following program will behave as follows during a dry run:
- The array arr[] stores 10 elements in such a way that arr[0]=1, arr[1]=2, arr[2]=3, and so on.
- The initialization of num is 8, which is the searchable number. Hence, num=8.
- Middle is initialized to first=0 and last=9 (first+last)/2 or 0+9/2 or 4. consequently middle=4
- The while loop’s condition is evaluated to be true since first’s value (zero) is smaller than last’s (nine). Consequently, program flow occurs inside of the loop.
- Determines if arr[middle] is false. As a result, the program flow enters the else if block and verifies its state.
- The evaluation of the condition arr[middle]==num or 8==8 is true. As a result, the sentences inside this if else block are executed.
- Prints the number’s location, in other words. due to the fact that the number is located at position 7. As a result, I reported its position as 8, as array indexing begins at 0, not at 1.
- To exit the while loop after reporting the element’s location, use the break keyword.
- Once the while loop has finished, the if block is used to determine whether the value of first is greater than the value of the last.
- If the condition is true, print a message indicating so.
- If the condition is true, print a message informing the user that the specified number cannot be found in the list.
Binary Search Programs in C++
Check the following Binary search program code by using the different method in C++
Method 1: Allow the User to Define the Size
With this program, the user may define the array size. Furthermore, it doesn’t care if the data are entered in ascending or random order. Because we created a piece of code that, after retrieving all the integers, arranges the list in ascending order (before doing the search function). then ask you to choose a searchable element from the sorted list, as seen in the following program.
Code Implementation of Binary Search in C++:
#include<iostream>
using namespace std;
int main()
{
int len, i, arr[50], num, j, temp, first, last, middle;
cout<<"Enter the Size: ";
cin>>len;
cout<<"Enter "<<len<<" Elements: ";
for(i=0; i<len; i++)
cin>>arr[i];
// sort the array first
for(i=0; i<(len-1); i++)
{
for(j=0; j<(len-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
// print the sorted array
cout<<"\nThe New Sorted Array is:\n";
for(i=0; i<len; i++)
cout<<arr[i]<<" ";
// now back to binary search
cout<<"\n\nEnter Element to be Search: ";
cin>>num;
first = 0;
last = (len-1);
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
{
cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
break;
}
else
last = middle-1;
middle = (first+last)/2;
}
if(first>last)
cout<<"\nThe number, "<<num<<" is not found in given Array";
cout<<endl;
return 0;
}
Input:
5
2 3 5 8 9
5Output:
Enter the Size: Enter 5 Elements:
The New Sorted Array is:
2 3 5 8 9
Enter Element to be Search:
The number, 5 found at Position 3Method 2: Using User-defined Function
BinSearRecFun(), a user-defined function that takes three parameters, is used to create this program. The array is the first item, followed by the number to be searched and the array’s size. This function either returns the element’s position in the list or 0 to denote that the requested number is not present in the list.
Before beginning the binary search, the provided array is sorted in ascending order using a method called sortArray().
Code Implementation of Binary Search in C++:
#include<iostream>
using namespace std;
void sortArray(int [], int);
int binSearchFun(int [], int, int);
int main()
{
int len, i, arr[50], num, pos;
cout<<"Enter the Size (max. 50): ";
cin>>len;
cout<<"Enter "<<len<<" Elements: ";
for(i=0; i<len; i++)
cin>>arr[i];
// sort the array first
sortArray(arr, len);
// print the sorted array
cout<<"\nThe New Sorted Array is:\n";
for(i=0; i<len; i++)
cout<<arr[i]<<" ";
cout<<"\n\nEnter Element to be Search: ";
cin>>num;
// search element using binary search
pos = binSearchFun(arr, num, len);
if(pos==0)
cout<<endl<<num<<" isn't available in the list";
else
cout<<endl<<num<<" is available at Position "<<pos;
cout<<endl;
return 0;
}
void sortArray(int arr[], int len)
{
int i, j, temp;
for(i=0; i<(len-1); i++)
{
for(j=0; j<(len-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int binSearchFun(int arr[], int num, int len)
{
int first, last, middle;
first = 0;
last = (len-1);
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
return (middle+1);
else
last = middle-1;
middle = (first+last)/2;
}
return 0;
}
Input:
5
10 20 30 40 50
30Output:
Enter the Size (max. 50): Enter 5 Elements:
The New Sorted Array is:
10 20 30 40 50
Enter Element to be Search:
30 is available at Position 3Method 3: Binary Search in C++ Using Recursion
This program uses recursion (a function that calls itself) to do a binary search on an element.
Code Implementation of Binary Search in C++:
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 20, 30, 40, 100, 400 };
int x = 30;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
Output:
Element is present at index 1Time Complexity of Binary Search in C++
| Scenario | Time Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(logn) |
| Worst Case | O(logn) |
Best Case Complexity of Binary Search in C++ – In a binary search, the best case scenario is when the searchable element is discovered in the first comparison, or when the first middle element is in fact the searchable element. Binary search has a best-case temporal complexity of O(1).
Average Case Complexity of Binary Search in C++ – For a binary search, the average case time complexity is O(logn).
Worst Case Complexity of Binary Search in C++ – The worst case scenario for binary search is when we have to continuously narrow the search space until there is just one element. Binary search has a worst-case temporal complexity of O(logn).
Space Complexity of Binary Search in C++
The Space complexity for coding binary search program in c++ is O(1).
Tips: On sorted array elements, binary search can be applied. We must first sort the list elements if they are not already organized in a sorted fashion.
Conclusion
In computer science and programming, binary search is a potent method that is frequently employed. Because it is substantially quicker than linear search and has a time complexity of O(log n), it is especially helpful for exploring enormous datasets.
This article may properly describe several methods of binary search in C++. We hope you learned something new from this post. Binary search techniques are frequently used in programming competition challenges to address challenging issues.
Frequently Asked Questions
FAQs on binary search in C++
Q1. How do I check if a target value is present in a sorted array using binary search in C++?
Ans. You can use the std::binary_search function provided by the C++ standard library. The function takes the beginning and end iterators of the array, as well as the target value to search for, and returns true if the target value is found, and false otherwise.
Q2. Can binary search in C++ be used for unsorted arrays?
Ans. No, binary search in C++ can only be used for sorted arrays. If the array is unsorted, the binary search algorithm will not work.
Q3. What is the difference between linear search and binary search?
Ans. Linear search checks each element in the input array until it finds the target element, while binary search repeatedly divides the search interval in half to eliminate the half of the array that cannot contain the target element.
Q4. What happens if the input array is empty in binary search in C++?
Ans. If the input array is empty, the binary search in the C++ algorithm will immediately return false since there is no element to search for.
Q5. Is it possible to use binary search for non-numeric values?
Ans. Yes, binary search can be used for non-numeric values as long as the values can be compared using comparison operators like "<" and ">".
Other C++ Programs.
C++ Program to Add Two Numbers
C++ Program to Reverse a Number
C++ program for heap sort
Bubble Sort in C++ with Program Code and Example
Hello world program in C++
Prime Number Program in C++
Factorial Program in C++