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

Popular posts from this blog

PERFECT SQUARE asked by MountainBlue

Harry and Porter asked in MountainBlue ,2022

Chomsky's hierarchy Explanation :