gallopSearch.cpp

template<typename T>
static const T *BinarySearch(const T *const first, const T *const last, const T value, std::function<int32_t(const T&, const T&)> cmp)
{
	const auto n = last  - first;
	int32_t top = n - 1, btm = 0;
   
	while (btm <= top)
	{
		const auto mid = (btm & top) + ((btm ^ top) >> 1);
		const auto p = first + mid;
		const auto v = *p;
		const auto d = cmp(value, v);

		if (d < 0)
			top = mid - 1;
		else if (!d)
			return p;
		else    
			btm = mid + 1;
	}
                   
	return last;
}


template<typename T>
static const T *GallopSearch(const T *const first, const T *const last, const T key, std::function<int32_t(const T &a, const T &b)> cmp)
{
	uint32_t i = 0, l = 0;
	const auto max = last - first;

	while (i < max)
	{
		const auto d = cmp(key, first[i]);

		if (d < 0)
			break;
		else if (!d)
			return first + i;
		else
		{
			l = i;
			i = (i << 1) + 1;
		}
	}

	if (i > max)
		i = max;

	const auto upto = first + i;
	const auto res  = BinarySearch(first + (l + 1), upto, key, cmp);

	return res == upto ? last : res;
}