Binary search time complexity

C++ code for binary search using loop

#include<iostream>
#include<conio.h>
using namespace std;
void main()
{
int arry[10]; int item; int n;
int loc=-1; int mid,start,end; start=0; end=9;
for(int i=0; i<10; i++)
{
cout<<“enter ur num = “;
cin>>arry[i];
}

cout<<endl<<endl;
for(int i=0; i<10; i++)
for(int j=0; j<9; j++)
if(arry[j]>arry[j+1])
{
item=arry[j];
arry[j]=arry[j+1];
arry[j+1]=item;
}

for(int i=0; i<10; i++)
{
cout<<“ur sorted arrry is = “<<arry[i]<<endl;
}
cout<<endl<<endl;

cout<<“enter num for searh = “;
cin>>n;
while(start<=end)
{
mid=(start+end)/2;

if(arry[mid]==n)
{ loc=mid;
break;
}
else
if(n<arry[mid])
end=mid-1;
else
start=mid+1;
}
cout<<endl;
if(loc==-1)

cout<<n<<“not found”<<endl;

else
cout<<n<<“found at index”<<loc<<endl;

getch();
}

C++ code for binary search using recursive function

#include<iostream>
#include<conio.h>
using namespace std;
int binarysearch(int start, int end, int arry[], int n )
{ int mid;
if(start>end)
return -1;
mid=(start+end)/2;
if(arry[mid]==n)
return mid;

else
if(n<arry[mid])
{end=mid-1;
return binarysearch(start,end,arry,n);}

else
{ start=mid+1;
return binarysearch(start,end,arry,n);
}
}

void main()
{ int start=0; int end=9; int arry[10]; int item,n; int p=0;
for(int i=0; i<10; i++)
{
cout<<“enter ur num”;
cin>>arry[i];
}
for(int i=0; i<10; i++)
for(int j=0; j<9; j++)
if(arry[j]>arry[j+1])
{
item=arry[j];
arry[j]=arry[j+1];
arry[j+1]=item;
}
cout<<endl<<endl;
for(int i=0; i<10; i++)
{ cout<<“ur sorted arry is “<<arry[i]<<endl; }

cout<<endl<<endl;
cout<<“enter ur num for search”;
cin>>n;

p=binarysearch(start,end,arry,n);

if(p==-1)
cout<<” value not found in array”;
else
cout<<n<<“value found in arry at index”<<p;
getch();
}

Analysis

• Loop starts with high-low=N-1
• Each time value of low-high is halved from the previous value
• If high-low = 32 the iteration go as 16, 8, 4,2,1
• So the running time is O(log N)