//logic - first we calculate the mid point of the array and then we check that where the search element exist ( before the mid or after the mid element ) . if search element exist before the mid element then we change the value of higher to mid-1 and if search element exist after the mid element then we change the value of lower to mid+1 and we do this process until lower is less than or equal to higher and value of mid element is not equal to search element. below is the Implementations of binary search.
//binary search
#include<iostream>
using namespace std;
int binarysearch(int arr[],int n,int search)
{
int lower=0;
int upper=n-1;
int mid=(lower+upper)/2;
while(lower<=upper){
if(search<arr[mid])
upper=mid-1;
else if(search>arr[mid])
lower=mid+1;
else if(arr[mid]==search){
return (mid+1);
}
mid=(lower+upper)/2;
}
return 0;
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int n=sizeof(arr)/sizeof(arr[0]);
int search;
cout<<"Enter element to search : ";
cin>>search;
int c,b;
b=binarysearch(arr,n,search);
if(b){
cout<<search<<" is found at "<<b<<" position.";
}
else
cout<<search<<" is not found.";
return 0;
}
Time complixity - O(log n)
Comments
Post a Comment