查找算法之二分查找

二分查找也叫折半查找，是一种非常高效的查找方法，但是这种查找方法有个大前提，需要数据有序。基本思路就是每次查找数据中间的位置，与目标值进行比较，每次可以排除一半的元素。这样时间复杂度为log2^n；

具体实现：

int BinarySearch(const vector& arr,int target)
{
	int left = 0;//确定左右边界
	int right = arr.size() - 1;
	int mid = (left + right) >> 1;//位运算代替除法
	while (left <= right) //注意是小于等于
	{
		if (arr[mid] == target)对应
			return mid; //找到元素，返回下标
		else if (arr[mid] > target)//由于mid已经比较过了，left和right的更新将跳过mid
			right = mid -1;
		else
			left = mid + 1;
		mid = (left + right) >> 1;
	}
	return -1;//走到这表明没有找到
}

测试用例 

1 2 3 4 5 6 7 8 9

查找目标

4

C++ STL库里算法头文件中，有这样的几个函数

他的作用是查找指定区域（[first, last) 前闭后开的区间）内不小于目标值的第一个元素。如果不存在，则返回的迭代器与last相同。

输入参数为一个区间和目标值。返回为一个迭代器。该函数不一定能找到目标值，可能是比他大的值。

用法和上面类似。

不过，他查找的是大于目标值的第一个元素。如果不存在返回值等于last。

用上面相同的测试用例

//vector arr1 = {1,2,3,4,5,6,7,8,9};
cout << *lower_bound(arr1.begin(), arr1.end(), 4)< 
 
返回的是迭代器，解引用就得到具体的值。
 
 
 
对于STL里面的容器，像set 和 map由于其底层是红黑树的结构，中序遍历出来是有序的数据。除此之外，由于其不支持随机访问（顺序存储结构），这种通用的二分查找的方法不适用。所以对于这类容器，有他们自己的二分查找方法。
 
 
 
 
 
 
 
 
 
输入参数都是key值，返回值为迭代器。
 
 
 
 
二分查找一些题目 
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
 
2250. 统计包含每个点的矩形数目 - 力扣（LeetCode）
 
2251. 花期内花的数目 - 力扣（LeetCode）
 
729. 我的日程安排表 I - 力扣（LeetCode）
 
对于需要二分查找的题目，部分题目会给出关键字眼 “有序”。还有一些题目需要我们自己进行自定义排序后再用二分查找。会提高不少的效率。