Overview of Binary Search
The binary search algorithm begins by comparing the target value to the value of the middle element of the sorted array. If the target value is equal to the middle element's value, then the position is returned and the search is finished. If the target value is less than the middle element's value, then the search continues on the lower half of the array; or if the target value is greater than the middle element's value, then the search continues on the upper half of the array. This process continues, eliminating half of the elements, and comparing the target value to the value of the middle element of the remaining elements - until the target value is either found (and its associated element position is returned), or until the entire array has been searched (and "not found" is returned).
Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection. Binary search locates the position of an item in a sorted array. Binary search compare an input search key to the middle element of the array and the comparison determines whether the element equals the input, less than the input or greater. The return value is the element position in the array.
Binary Search Algorithm complexity
- Worst case performance O(log n)
- Best case performance O(1)
- Average case performance O(log n)
- Worst case space complexity O(1)
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.
Iterative implementation of Binary Search
#include<iostream>
using namespace std;
// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
if (arr[m] == x) return m; // Check if x is present at mid
if (arr[m] < x) l = m + 1; // If x greater, ignore left half
else r = m - 1; // If x is smaller, ignore right half
}
return -1; // if we reach here, then element was not present
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);// calculate array size
int x ;
//print array
for (int i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n\nEnter a number to Search: ";
cin>>x;
int result = binarySearch(arr, 0, n-1, x);
if (result==-1)
{
cout<<"\nElement is not found in array"<<endl;
}
else
{
cout<<"\nElement is found at index:==> "<< result<<endl;
}
return 0;
}
::Output ::
Recursive implementation of Binary Search
#include<iostream>
using namespace std;
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if (arr[mid] == x) return mid;
// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present in array
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);// calculate array size
int x ;
//print array
for (int i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n\nEnter a number to Search: ";
cin>>x;
int result = binarySearch(arr, 0, n-1, x);
if (result==-1)
{
cout<<"\nElement is not found in array"<<endl;
}
else
{
cout<<"\nElement is found at index:==> "<< result<<endl;
}
return 0;
}
::Output ::
OR 