Open Mobile Map

Binary Search Algorithms

The Binary search requires an ordered list.  You can use Heap Sort Algorithm to sort the list first.

Iterative Algorithm
int find (const apvector &list, double target)
// pre: list is sorted in ascending order
//post: ITERATIVE binary search will return the index of the target element, else -1

{
	int mid;
	int first = 0;
	int last = list.length( ) -1;
	while ( first <= last )
	{
		mid = (first + last) / 2;
		if ( list[mid] == target )
			return mid;
		if ( list[mid] > target )
			last = mid - 1;
		else	first = mid + 1;
	}
	return -1;
}

Recursive Algorithm
int find (const apvector &list, double target, int first, int last)
// pre: list is sorted in ascending order
//post: RECURSIVE binary search will return the index of the target element, else -1

{
	if (first > last)
		return -1;

int mid = (first + last) / 2;
	if (list[mid] == target)
		return mid;

if (list[mid] < target)
		return find(list, target, mid+1, last);

return find(list, target, first, mid-1);

}