## Wednesday 8 November 2017

### Binary search recursive and non recursive implementation in c++

In this post, we will see Recursive as well as Non-Recursive implementation of Binary Search in C++ language.

Time Complexity of Binary Search is O(log n).

Program (binarysearch.cpp)
 #include using namespace std; //Non-recursive binary search int binarysearch(int arr[],int left,int right, int item)  {   int middle;   int size=right-left+1;   while(left<=right)    {     middle = ((left + right)/2);     if(item == arr[middle])      {       return(middle);      }     if(item > arr[middle])      {       left = middle+1;      }     else      {       right = middle-1;      }    }   return(-1);  } //Recursive binary search int binarysearchrecursive(int arr[],int left,int right, int item)  {   int middle;   int size=right-left+1;   if(left<=right)    {     middle = ((left + right)/2);     if(item == arr[middle])      {       return(middle);      }     if(item > arr[middle])      {       left = middle+1;       binarysearchrecursive(arr,left,right,item);      }     else      {       right = middle-1;       binarysearchrecursive(arr,left,right,item);      }   }  else   {     return(-1);    }  } //main() function int main()  {   int arr,size,i,j,item,index,choice;   cout<<"Enter total number of elements of array\n";   cin>>size;   cout<<"Enter the elements of array in sorted order:\n";   for(i=0;i>arr[i];    }    cout<<"Enter the element to be searched:\n";    cin>>item;   //Menu Driven   cout<<"\nEnter the choice\n"<<"1.Recursive\n"<<"2.Non-Recursive\n";   cin>>choice;   //Recursive   if(choice==1)   index=binarysearchrecursive(arr,0,size-1,item);   //Non-recursive   if(choice==2)   index=binarysearch(arr,0,size-1,item);   if(index!=-1)    {     cout<<"\n";     cout<<"The index of element to be searched:";     cout<<"\n"<

Output (Recursive Binary Search):
 parag@parag-Inspiron-N4010:~/Desktop/programs\$ g++ binarysearch.cpp parag@parag-Inspiron-N4010:~/Desktop/programs\$ ./a.out Enter total number of elements of array 7 Enter the elements of array in sorted order: 12 14 15 20 22 26 36 Enter the element to be searched: 22 Enter the choice 1.Recursive 2.Non-Recursive 1 The index of element to be searched: 4

Output (Non-Recursive Binary Search):

 parag@parag-Inspiron-N4010:~/Desktop/programs\$ g++ binarysearch.cpp parag@parag-Inspiron-N4010:~/Desktop/programs\$ ./a.out Enter total number of elements of array 7 Enter the elements of array in sorted order: 12 14 15 20 22 26 36 Enter the element to be searched: 22 Enter the choice 1.Recursive 2.Non-Recursive 2 The index of element to be searched: 4