C++: Binary Search

Bjarne-stroustrup
 

//! \brief A recursive binary search using STL vectors
//! \param vec The vector whose elements are to be searched
//! \param start The index of the first element in the vector
//! \param end The index of the last element in the vector
//! \param key The value being searched for
//! \return The index into the vector where the value is located,
//! or -1 if the value could not be found.
template<typename T>
int binary_search(const std::vector<T>& vec, unsigned start, unsigned end, const T& key)
{
	// Termination condition: start index greater than end index
	if(start > end)
	{
		return -1;
	}

	// Find the middle element of the vector and use that for splitting
	// the array into two pieces.
	const unsigned middle = start + ((end - start) / 2);

	if(vec[middle] == key)
	{
		return middle;
	}
	else if(vec[middle] > key)
	{
		return binary_search(vec, start, middle - 1, key);
	}

	return binary_search(vec, middle + 1, end, key);
}

SOURCE