This article is about binary search and its implementation in C++.
Table of Contents
What is Binary Search?
The word ‘Binary’ actually refers to ‘two’. So, it’s anticipatable that there will be something related to ‘two’. In case of linear search, we start from the beginning of an array and keep checking gradually.
Now, there may be cases that the searching element belongs to the end part of an array and we kept wasting our time checking all the other elements incase of the linear search. For any searching algorithm what matters most is its time complexity. Though the linear search with its complexity O(n) seems to do pretty well, it’s actually not. Just think of any large data set, how much time it will take, though it’s O(n). We can’t afford such. Here comes the binary search with much less time complexity.
Binary search is based on the idea of sorting. For operating binary search, the input array needs to be sorted. So, the idea is, we can start with the middle element. If the searching element is less than the middle element, there’s no need to check the elements on the right half of the middle element, i.e., we can skip the elements larger than middle element. Since the array is sorted, it’s guaranteed no element on the right side can be the searching element.
On the other hand, If the searching element is greater than the middle element, there’s no need to check the elements on the left half of the middle element, i.e., we can skip the elements smaller than middle element. Since the array is sorted it’s guaranteed no element on the left side can be the searching element.
Binary search algorithm
Considering 0-indexing,
- Initialize a variable left=0
- Initialize a variable right=array size – 1
- While left <= right
Do
Calculate mid= (left + right)/2
If array[mid]==searching element
Return True
Else If array[mid] < searching element
Set left=mid +1
Else //array[mid] > searching element
Set right=mid –1
END While - Return False
Time Complexity
O(logn)
For binary search the recursion relation is;
T(n)=T(n/2)+ O(1)
(As we always search only in one half)
Solving the recursion relation, we find time complexity to be O(logn)
Example with explanation
Let the input array be:
1, 2, 3, 4, 5, 6
Let the searching element be: 2
So,
Left=0
Right=5 (array size=6)
Iteration 1
Left<right
Mid=(0+5)/2 = 2
Array[mid]>2
So, left=0
Right=mid-1=1
Iteration 2
Left<right
Mid=(0+1)/2 = 0
Array[mid]<2
So, left=mid+1=1
Right=1
Iteration 3
 Left=right
Mid=(1+1)/2 = 1
Array[mid]==2
Return True
Searching element found
Binary search C++ implementation<
Iterative solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> using namespace std; int binarySearch(vector<int> a,int n, int x){ int left=0; //initialize left int right=n-1; //initialize right int mid; while(left<=right){ mid=(left+right)/2; //calculate mid if(a[mid]==x) //if the a[mid] is x value is found return 1; else if(a[mid]<x){ //if a[mid] is less than x, we need to search only the right half left=mid+1; } else //if a[mid] is less than x, we need to search only the left half right=mid-1; } //if not returned from the loop, it ensures value is not present return -1; } int main(){ int n,item,x; cout<<"Enter number of elements in the array\n"; cin>>n; vector<int> a; //input the array cout<<"Enter the elements of your array\n"; for(int j=0;j<n;j++){ scanf("%d",&item); a.push_back(item); } cout<<"Enter the value you want to search\n"; cin>>x; int result=binarySearch(a,n,x); //function to output search result if(result!=-1) cout<<x<<" is present in the array"<<endl; else cout<<x<<" is not present in the array"<<endl; return 0; } |
Output:
6
Enter the elements of your array
4 6 8 9 10 11
Enter the value you want to search
11
11 is present in the array
Recursive solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <bits/stdc++.h> using namespace std; int binarySearch(vector<int> a,int left,int right, int x){ if(left>right) return -1; int mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) return binarySearch(a,mid+1,right,x);//search in the right half else return binarySearch(a,left,mid-1,x);//search in the left half } int main(){ int n,item,x; cout<<"Enter number of elements in the array\n"; cin>>n; vector<int> a; //input the array cout<<"Enter the elements of your array\n"; for(int j=0;j<n;j++){ scanf("%d",&item); a.push_back(item); } cout<<"Enter the value you want to search\n"; cin>>x; int result=binarySearch(a,0,n-1,x); //function to output search result if(result!=-1) cout<<x<<" is present in the array"<<endl; else cout<<x<<" is not present in the array"<<endl; return 0; } |
Output:
3
Enter the elements of your array
4 7 9
Enter the value you want to search
6
6 is not present in the array
That’s all about Binary search in C++
