Finds a string in a sequence of sorted strings interspersed with empty ones.

find_with_empty.cpp

template<typename Iterator, typename T>
bool find_with_empty(Iterator begin, Iterator end, const T& value)
{
	if (begin == end || value < *begin || value > *std::prev(end))
	{
		return false;
	}
	
	auto middle = begin;
	
	std::advance(middle, std::distance(begin, end)/2);
	
	if (! middle->empty())
	{
		if (value < *middle)
		{
			return find_with_empty(begin, middle, value);
		}
		
		else if (value > *middle)
		{
			return find_with_empty(++middle, end, value);
		}
		
		else return true;
	}
	
	else
	{
		auto i = middle, j = middle;
		
		for (auto stop = std::prev(end); i->empty() && j->empty(); )
		{
			if (i == begin && j == stop) return false;
			
			if (i != begin) --i;
			
			if (j != stop) ++j;
		}
		
		if ((! i->empty() && *i == value) ||
			(! j->empty() && *j == value)) return true;
		
		if (! i->empty())
		{
			if (value < *i)
			{
				return find_with_empty(begin, i, value);
			}
			
			else return find_with_empty(j, end, value);
		}
		
		if (! j->empty())
		{
			if (value > *j)
			{
				return find_with_empty(++j, end, value);
			}
			
			else return find_with_empty(begin, i, value);
		}
	}
	
	return false;
}