C++: Binary Search


//! \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);