//PROGRAM CODE 9.3

#include<iostream.h>
#include<conio.h>

int Binary_Search_non_recursive(int A[], int n, int key)
{
int low=0,high=n-1,mid;
while(low<=high)
{ //iterate while first<=last
mid = (low + high)/2; //calculate
//mid = (first+last)/2)
if(A[mid] == key) //found
return mid; // return position (mid)
else if(key<A[mid])
//not found-look in upper half of list
high=mid-1;
else
low=mid+1; //look in lower half
}
return -1; //return "not found"
}

void main()
{
int i, size,A[20],ans,key;
clrscr();
cout<<"Enter array size = ";
cin>>size;

cout<<"\n Enter array elements";
for (i=0;i<size;i++)
{
cin>>A[i];
}
cout<<"\n\n\t Enter the element to be search = ";
cin>>key;
ans =Binary_Search_non_recursive(A,size,key);
if(ans==-1)
	cout<<"\n Not found";
else
	cout<<"Found";

getch();
}

/*********************OUTPUT *******************************
Enter array size = 5

 Enter array elements
1 2 3 4 5

	 Enter the element to be search = 5

Found

Enter array size = 5

 Enter array elements
1 2 3 4 5

	 Enter the element to be search = 25

Not Found

***********************************************************/