c++ stl二分查找与lower_bound

本文主要是介绍c++ stl二分查找与lower_bound，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. binary_search实现

int myBinary_search(int arr[], int n, int target)
{
	int first = 0, last = n;
	int mid;
	while (first < last)
	{
		mid = first + (last - first) / 2;
		if (arr[mid] == target) 
		{
			return mid;
		}
		else if ( target > arr[mid] )
		{
			first = ++mid;
		}
		else
		{
			last = mid;
		}
	}
	return -1;
}

void test()
{
	int arr[] = { 5,7,7,8,8,10 };
	cout << myBinary_search(arr, 6, 1) << endl;	//-1
	cout << myBinary_search(arr, 6, 5) << endl;	//0
	cout << myBinary_search(arr, 6, 8) << endl;	//3
	cout << myBinary_search(arr, 6, 10) << endl;//5
}

2. lower_bound实现

template<typename ForwardIter, typename T>
ForwardIter myLower_bound(ForwardIter first, ForwardIter last, T value)
{
	while (first != last)
	{
		auto mid = next(first, distance(first, last) / 2);
		if (value > *mid) first = ++mid;
		else last = mid;
	}
	return first;
}

template<typename ForwardIter, typename T>
ForwardIter myUpper_bound(ForwardIter first, ForwardIter last, T value)
{
	while (first != last)
	{
		auto mid = next(first, distance(first, last) / 2);
		if (value >= *mid) first = ++mid;
		else last = mid;
	}
	return first;
}

3. cppreference.com

//可能的实现
//版本一
template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}
 
//版本二
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) && !(comp(value, *first)));
}

myBinary_search根据lower_bound实现

这篇关于c++ stl二分查找与lower_bound的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！