Code for Binary Search - C++

-: Binary Search with intermediate steps:-

Binary Search works on the sorted lists only. At each step number of items under consideration becomes less than the previous list. 

1. The main concept is that item_to_be_searched is checked with the middle item, if the item_to_be_searched is smaller than the middle item then the first half of the list is processed. Otherwise, the second half of the list is being processed. 

2. Keep on doing this until the item_to_be_searched is being found (or the whole list is being processed and the item is not there).

The complexity of Binary Search:- Log₂ N

Here is the code for it:- For ease of understanding, I have written the code which will not only give you the location of item_to_be_searched but also give you intermediate steps so that you can do the dry run along with the compiler.

                                           

CODE:-

#include<stdio.h>

#include<iostream>

using namespace std;

int main()

{

int n,i,a,low, high, mid;

cout<<"Enter the number of elements: ";

cin>>n;

int array[n];

printf("Enter the elements in a sorted manner: \n");

for(i=0;i<n;i++)

cin>>array[i];

cout<<"Enter the value to find: ";

cin>>a;

low=0;

high=n-1;

mid=(low+high)/2;

cout<<"low is "<<low<<endl;

cout<<"mid is "<<mid<<endl;

cout<<"high is"<<high<<endl;

cout<<endl;

while (low<=high)

{

if(array[mid]<a)

{ low=mid+1;

cout<<"low is "<<low<<endl;

cout<<"mid is "<<mid<<endl;

cout<<"high is"<<high<<endl;

cout<<endl;

}

else if(array[mid] ==a)

{

cout<<a<<" found at the location "<<mid+1;

break;

cout<<"low is "<<low<<endl;

cout<<"mid is "<<mid<<endl;

cout<<"high is"<<high<<endl;

cout<<endl;

}

else

high=mid-1;

mid=(low+high)/2;

cout<<"low is "<<low<<endl;

cout<<"mid is "<<mid<<endl;

cout<<"high is"<<high<<endl;

cout<<endl;

}

if(low>high)

cout<<a<<" is not present in the array ";

return 0;

}

OUTPUT:-

Related Post