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<iostream>
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[20],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<size;i++)
   {
    cin>>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"<<index;
   }
  else
  {
   cout<<"\nThe element to be searched is not found\n";
  }

  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



Output (Element Not Found):
parag@parag-Inspiron-N4010:~/Desktop/programs$ g++ binarysearch.cpp
parag@parag-Inspiron-N4010:~/Desktop/programs$ ./a.out
Enter total number of elements of array
8
Enter the elements of array in sorted order:
13 22 32 43 53 57 79 98
Enter the element to be searched:
51

Enter the choice
1.Recursive
2.Non-Recursive
1

The element to be searched is not found



                     Check other posts on Data Structures in this link http://www.comrevo.com/2016/09/data-structures.html.

No comments:

Post a comment