【极简数据结构03】向量的二分查找

如果我们需要对一个vector进行二分查找，和数组的写法有点区别：

向量和数组的一个不同点在于，vector中的元素区间是左闭右开，初始查找状态如下：

后续的迭代方法就和数组中的二分查找类似，我就不再过多的推导

代码如下：

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

template <typename T>
bool binary_search_vector (const T & key , typename vector<T> :: const_iterator data , size_t N)  //第二个参数是一个向量中的常量迭代器 
{
	size_t low = 0;
	size_t high = N;
	
	while(low < high)   //循环条件和数组中的略有不同
	{
		size_t middle = low + (high - low) / 2;
		
		if(key < *(data + middle))
			high = middle;
			
		else if(*(data + middle) < key)
			low = middle + 1;
		
		else
			return true;
	}
	
	return false; 
}
 
int main()
{
	vector<int> v = {1,2,3,4,5};
	cout << binary_search_vector(2 , v.cbegin() , 5);
	cout << binary_search_vector(0 , v.cbegin() , 5);
	cout << binary_search_vector(2 , v.cbegin() + 2 , 3);
	cout << binary_search_vector(0 , v.cbegin() , 0);
	return 0; 
	
}

总结：其实不论是数组的二分查找还是向量的二分查找，它们的世家复杂度都是一样的，分析一下就能知道它们是O(logn)，比一般的遍历查找速度快了很多，也推荐大家在平时的编程和比赛中多使用二分查找。