fbpx

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

Our team found a curious site for our readers that are fans of online gaming, a rather exciting site that provides the latest gaming technology. Casinodots.com is the site, they compile the best reviews of MGA casino utan svensk licens sites. This site might pique your curiosity and you can win extra money!