*
int iterative_binary_search(int Arr[],int firstIndex,int lastIndex,int item)
{
while(firstIndex<=lastIndex)
{
int mid=(firstIndex+lastIndex)/2;
if(item<Arr[mid])
{
lastIndex=mid-1;
}
else if(item>Arr[mid])
{
firstIndex=mid+1;
}
else //when Arr[mid]==desired item
{
return mid;
}
}
//we will reach here,when we failed to find our item in array
return -1;
}
#include<iostream>
using namespace std;
int iterative_binary_search(int Arr[],int firstIndex,int lastIndex,int item)
{
while(firstIndex<=lastIndex)
{
int mid=(firstIndex+lastIndex)/2;
if(item<Arr[mid])
{
lastIndex=mid-1;
}
else if(item>Arr[mid])
{
firstIndex=mid+1;
}
else //when mid==desired item
{
return mid;
}
}
return -1;
}
int main()
{
int n,x,result;
int n,x,result;
cout<<"Sir,please enter the size of array :\n";
cin>>n;
int Arr[n];
cout<<"Enter the elements of array :\n";
for(int i=0;i<n;i++)
{
cin>>Arr[i];
}
cout<<"Enter the number you wanna search :\n";
cin>>x;
result=(Arr,0,n-1,x);
if(result==-1)
{
cout<<"OPPS...!!! item not found..!!!"<<endl;
}
else
{
cout<<"Item found at index :"<<result;
}
return 0;
}
Implementation in Code :
Complexity of Binary_Search:
Time: O(log n) [worstCase]
Space: O(1)
Time: O(log n) [worstCase]
Space: O(1)
To know more clearly about complexity Click here
Quote: