Binary Search C++

Updated April 7, 2023

Introduction to Binary Search C++

In any programming language, search is an important feature. Binary search is a method of finding an element in an array by sorting the array and then dividing the array into half, till the number is found. It is a sorting algorithm. If the item being searched is less than the item in the middle, then the upper portion of the interval is searched else the lower half is considered. This is carried out till the number is found. This article will explain in detail binary search in c++ along with appropriate examples.

Syntax:

binary_search(startadd, endadd, numbertofind)

Parameters:

• startadd: First elements address in the array
• endadd: Last elements address in the array
• numbertofind: The number to be searched for

Returns:

If the element is found, true is returned else false is returned.

Steps:

• Before the search begins, the array should be sorted.
• The elements of the array should be divided into half
• The middle element is taken. If it equals the number that is searched, then the search is ended.
• If the element is less than the middle value, then the top half(left half) is considered.
• If the element is greater than the middle value, then the bottom half(right half) is considered.

Example of Binary Search in C++

Code:

#include <iostream>
using namespace std;
int bs(int[], int, int, int);
int main()
{
int ip[10] = {10, 22, 37, 55, 92, 118};
int sip, lo=-1;
cout<<"Demo of binary search in C++";
cout<<"\nEnter the element to search ";
cin>>sip;
lo = bs(ip, 0, 6, sip);
if(lo != -1)
{
cout<<"Element found in the position "<<lo;
}
else
{
cout<<"Element is not found in the array";
}
return 0;
}
int bs(int a[], int fi, int la, int sip)
{
int mid;
if(la >= fi)
{
mid = (fi + la)/2;
if(a[mid] == sip)
{
return mid+1;
}
else if(a[mid] < sip)
{
return bs(a,mid+1,la,sip);
}
else
{
return bs(a,fi,mid-1,sip);
}
}
return -1;
}

Output:

There are two ways to implement a binary search. Iteration and recursive method.

Iteration method pseudocode

does until the least and max pointers meet.

mlevel = (least + max)/2
if (x == arr[mlevel])
return mlevel
else if (x > arr[mlevel])
least = mlevel + 1
else
max = mlevel – 1

Recursive method

bfs(arr, x, least, max)
if least > max
return False
else
mid = (least + max) / 2
if x == arr[mid]
return mid
else if x > arr[mid]
return bfs(arr, x, mid + 1, max)
else
return bfs(arr, x, least, mid - 1)

Complexities of Binary Search

The following are the time complexities of binary search.

The best-case time complexity of binary search is 0(1). The average and worst-case complexity are o(log n). The space complexity of binary search is 0(1).

Example – Iterative search

Code:

#include <iostream>
using namespace std;
int bfs(int tes[], int a, int b, int z)
{
while (a <= b) {
int n = a + (b - a) / 2;
if (tes[n] == z)
return n;
if (tes[n] < z)
a = n + 1;
else
b = n - 1;
}
return -1;
}
int main(void)
{
int tes[] = { 2, 3, 4, 10, 40 };
int z ;
cout<<"\nEnter the element to search ";
cin>>z;
int n = sizeof(tes) / sizeof(tes[0]);
int besuat = bfs(tes, 0, n - 1, z);
(besuat == -1) ? cout << "Input is not part of array"
: cout << "Input is present at the position " << besuat;
return 0;
}

Output:

Advantages of Binary Search

• Instead of searching the whole lo, in the first step itself half of the search list is eliminated.
• It is easy to identify whether the element that is being searched is before or after the position of the current element in the list.
• This can be easily used to reduce the search and improve the speed.
• When compared to linear search it is more efficient in searching data in a large list.
• It is possible to identify in each step, which sub-tree contains the desired element.
• It is more efficient than arrays and linked lists.
• The deletion and insertion take place quickly when compared with other data structures such as linked lists or arrays.

Disadvantages of Binary Search

• Since the recursive method is used for searching more stack space is required which is a major disadvantage
• This technique is much more prone to errors and difficult to debug in case of errors
• This provides poor caching of memory.
• It is very much time-consuming because of recursive calls.

Real-life examples of Binary Search

• The major example of binary search is the way we use dictionaries. To find a word, we randomly check for a word and move based on that word.
• Similarly, to find the minimum ad maximum size that is needed for an office to accommodate the staff we can easily do a binary search to arrive at the size by halving the available list.
• Selecting students based on height when the students are not particularly aware of their height.
• Checking for books in a library as books are arranged in order.
• Opening a page number in a book in random order.
• Accessing student’s information in a university database. This is very helpful because generally information is sorted and stored and since there would be a huge number of student’s information at the first step itself dataset is halved.

Conclusion

Thus, the article covered in detail about binary search in detail. It explained the syntax, parameters, steps along with proper illustrations. The article explained in detail both the ways binary search can be implemented and showed them with pseudocode. It also explained the real-world scenarios and explained with proper examples. It can be understood more in detail by practicing sample programs.

Recommended Articles

This is a guide to Binary Search C++. Here we discuss the Introduction, syntax, and parameters, examples with code implementation. You may also have a look at the following articles to learn more –

1. C++ getline()
2. C++ Expression
3. C++ pair
4. C++ this