二分查找

binarysearcha.cpp

/*
lower_bound:Returns an iterator pointing to the first element in the range [first,last) 
			which does not compare less than val.
upper_bound:Returns an iterator pointing to the first element in the range [first,last)
			which compares greater than val.
*/


#include <iostream>
#include <iterator>
using namespace std;

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::difference_type count, step;
	count = distance(first, last);
	while (count>0)
	{
		it = first; step = count / 2; advance(it, step);
		if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
			first = ++it;
			count -= step + 1;
		}
		else count = step;
	}
	return first;
}

template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits<ForwardIterator>::difference_type count, step;
	count = distance(first, last);
	while (count>0)
	{
		it = first; step = count / 2; advance(it, step);
		if (!(val < *it)) {                 // or: if (comp(*it,val)), for version (2)
			first = ++it;
			count -= step + 1;
		}
		else count = step;
	}
	return first;
}

int *my_lower_bound(int *first, int *last, const int val)
{
	int count = last - first, mid = count / 2;
	if (count == 0)
	{
		return first;
	}
	if (*(first + mid) < val)
	{
		return my_lower_bound(first + mid + 1, last, val);
	} 
	else
	{
		return my_lower_bound(first, first + mid, val);
	}
}

int *my_upper_bound(int *first, int *last, const int val)
{
	int count = last - first, mid = count / 2;
	if (count == 0)
	{
		return first;
	}
	if (*(first + mid) <= val)
	{
		return my_upper_bound(first + mid + 1, last, val);
	}
	else
	{
		return my_upper_bound(first, first + mid, val);
	}
}

int *my_binary_search(int *first, int *last, const int val)
{
	int count = last - first, mid = count / 2;
	if (count == 0)
	{
		return first;
	}
	if (*(first + mid) == val)
	{
		return first + mid;
	}
	else if (*(first + mid) < val)
	{
		return my_upper_bound(first + mid + 1, last, val);
	}
	else
	{
		return my_upper_bound(first, first + mid, val);
	}
}

int main()
{
	//int a[] = { 10, 10, 20, 20, 20, 30, 30 };
	//int a[] = { 10, 10, 21, 21 ,21 ,30 , 30 };
	//int a[] = { 10, 10, 11, 11 ,11 ,12 , 12 };
	int a[] = { 30, 30, 31, 31 ,31 ,32 , 32 };

	int *result = lower_bound(a, a + 7, 20);

	std::cout << "result: " << *result << " pos: " << result - a << endl;

	result = my_lower_bound(a, a + 7, 20);

	std::cout << "result: " << *result << " pos: " << result - a << endl;


	// upper

	result = upper_bound(a, a + 7, 20);

	std::cout << "result: " << *result << " pos: " << result - a << endl;

	result = my_upper_bound(a, a + 7, 20);

	std::cout << "result: " << *result << " pos: " << result - a << endl;


	// binary search


	return 0;
}