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;

}