Algorithm:
1. Set beg=0,last=12
2. REPEAT steps 3 through 6 UNTIL beg>last //INT() is used to extract integer part
3. mid=INT((beg+last)/2)
4. if A[mid]==ITEM then
{
print "Search Successful"
print ITEM,"fount at",mid
break /* go out of the loop*/
}
5. if A[mid]ITEM then
last=mid-1 /* END of repeat */
7. if beg!=last
print "Unsuccessful Search"
8. END
Intermediate Results:
(i) Search for 66.
Step 1: beg=1; last=13; mid=INT(1+13)/2=7
Step 2: A[mid] i.e., A[7] is 45 45<66 then
beg=mid+1 i.e., beg=7+1=8
Step 3: mid=Int((beg+last)/2)=INT((8+13)/2)=10
A[10] i.e., 89>66 then last = mid-1=10-1=9
Step 4: mid=((8+9)/2)=8
A[8] is 71 71>66 than last = mid-1=8-1=7
Step 5: mid=((8+7)/2)=7
A[7] is 45 45 < 66 then beg = mid+1=7+1=8
Step 6: mid=((8+8)/2)=8 (beg=last=8)
A[8] is 71 => 71!=66
“Search Unsuccessful!!!”
(ii) Search for 71.
Step 1: beg=1; last=13; mid=INT(1+13)/2=7
Step 2: A[mid] i.e., A[7] is
45 45<71 then
beg=mid+1 i.e., beg=7+1=8
Step 3:
mid=Int((beg+last)/2)=INT((8+13)/2)=10
A[10] i.e., 89>71 then last = mid-1=10-1=9
Step 4: mid=((8+9)/2)=8
A[8] is 71 71=>71
“Search Successful!!!”
Program:
#include<iostream.h>
int Bsearch(int [],int);
int main()
{ int A[]={3,4,7,11,18,29,45,71,87,89,93,96,99};
int index;
index=Bsearch(A,71);
if(index==-1)
cout<<"Element not found..";
else
cout<<"Element found at
index:"<A[mid]) beg=mid+1; else last=mid-1; }
rerurn -1;
}
int Bsearch(int A[],int item)
{ int beg,last,mid;
beg=0; last=13-1;
while(beg<=last)
{ mid=(beg+last)/2;
if(item==A[mid]) return mid;
else if (item>A[mid]) beg=mid+1;
else last=mid-1;
}
rerurn -1;
}
