#include <iostream.h>
int binarySearch(int[],int,int,int);

int main()
{
	int values[] = {2,5,7,8,11,15,22,29,40,43,69,80};
	int loc;

	loc = binarySearch(values,0,11,43);
	if (loc != -1)
		cout << "Number 43 was found in location " << loc << endl;
	else
		cout << "Number 43 is not in the array\n";

	loc = binarySearch(values,0,11,6);
	if (loc != -1)
		cout << "Number 6 was found in location " << loc << endl;
	else
		cout << "Number 6 is not in the array\n";
}

//  searches arr from positions first through last for value
//  preconds:	0 <= first, last <= size-1, size is max size of arr
//			arr[first] <= arr[first+1] <= ... <= arr[last]
//  postconds:	if value is in arr, returns loc where value was found
//			if value is not in arr, returns -1
//			all parms are unchanged

int binarySearch(int arr[], int first, int last, int value)
{
	if (first > last)
		return -1;
	else
	{
		int mid = (first + last) / 2;
		if (value == arr[mid])
			return mid;
		else if (value < arr[mid])
			return binarySearch(arr,first,mid-1,value);
		else
			return binarySearch(arr,mid+1,last,value);
	}
}

Number 43 was found in array location 9
Number 6 is not in the array

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page