Binary search on an array of integer without using Recurssion :
This will execute in O(log(N)) time where N is the size of array and it will use constant space size ,but binary search with recursion uses O(log(N)) stack size. the code
#include <iostream>
using namespace std;
int main()
{
int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
int n = sizeof(a)/sizeof(a[0]);
int i = 0;
int j = n-1;
int x=12,f=0;
while(i<=j)
{
if(i==j && a[i] == x)
{
cout<< " found " <<a[i] << " at " <<i;
f =1;
return 0;
}
int mid = (i+j)/2;
if(a[mid] == x)
{
cout << " found " <<a[mid] << " at " <<mid;
f=1;
return 0;
}
if(x < a[mid])
j = mid - 1;
else
i = mid + 1 ;
}
if( f==0)
cout<<"not present";
}
Comments
Post a Comment