再遇【二分查找】

• • 1、概述
  • 2、二分查找的原理
  • 3、二分查找实现
  • • 3.1 查找指定值
    • 3.2 查找>=target的最小下标
    • 3.3 查找<=target的最大下标
  • 4、总结

在进行算法刷题时经常会用到一类算法那就是二分查找，针对一组有序数组，查找到对应元素或者满足某些条件的元素的下标等等，这就需要用到今天的 二分查找算法。

我所理解的二分查找，也叫折半查找，每次查找一些元素还是什么的，都是根据条件先缩短在一半的范围内，然后再在这一半的范围内根据条件，再缩短，直至找到需要的元素，或者搜寻的范围为空。

这里的是自己写的利用双指针实现的二分查找，当然可以使用 C++11 texttt{C++11} C++11 中的一些函数调用来实现但是对于我这种初学者来说，多写写还是好处多多的。

// 双指针二分查找
int binarySearch(vector& nums, int target) {
	sort(nums.begin(), nums.end());		// 二分查找要求数组有序
	int n = nums.size();
	int l = 0, r = n - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (nums[mid] > target) {
			--r;
		}
		else if (nums[mid] < target) {
			++l;
		}
		else {
			return mid;
		}
	}
}

// 查找比target大的最小下标
int getBiggerThanTarget(vector& nums, int target) {
	sort(nums.begin(), nums.end());
	int n = nums.size();
	int ans = -1;						// 二分查找要考虑到ans初始化情况，可以初始化为-1
	int l = 0, r = n - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (nums[mid] >= target) {		// 把这里的=去掉就是查找 >target的最小下标值
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	// 通过判断 ans 是否为-1，可以判断是否存在 >=target的最小下标
	return ans;
}

也可以使用 lower_bound(nums.begin(), nums.end(), target)
来实现查找 >=   target texttt{>= target} >= target 的最小下标, 通过解引用可以得到对应的元素，
通过 lower_bound(nums.begin(),   nums.end(),   target)   -   nums.begin() texttt{lower_bound(nums.begin(), nums.end(), target) - nums.begin()} lower_bound(nums.begin(), nums.end(), target) - nums.begin() 来获取下标.

还有一个 texttt{还有一个} 还有一个：

upper_bound(nums.begin(), nums.end(), target)
来实现查找 >   target texttt{> target} > target 的最小下标, 参考文档里的原话是：
Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.
通过解引用可以得到对应的元素，
通过 upper_bound(nums.begin(),   nums.end(),   target)   -   nums.begin() texttt{upper_bound(nums.begin(), nums.end(), target) - nums.begin()} upper_bound(nums.begin(), nums.end(), target) - nums.begin() 来获取下标.

// 查找比target大的最小下标
int getBiggerThanTarget(vector& nums, int target) {
	sort(nums.begin(), nums.end());
	int n = nums.size();
	int ans = -1;						// 二分查找要考虑到ans初始化情况，可以初始化为-1
	int l = 0, r = n - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (nums[mid] <= target) {		// 把这里的=去掉就是查找 
			l = mid + 1;
		}
	}
	// 通过判断 ans 是否为-1，可以判断是否存在 <=target的最大下标
	return ans;
}

（1）、无论是哪种编程语言的学习都离不开对于数据结构的学习，在边学边用过程中，总会有一些算法，比如二分查找，第一次学习的时候感觉已经学的很顺了，但是在某一次使用解题的过程中会发觉，写的不顺了，逻辑不通了，错误百出了，对于经典算法没有肌肉记忆了，这个时候就是我们回过头再次学习的时候了；
（2）、学会查询一些官方说明文档，比如 C++ Reference，Python Reference，这些都是一手资料，比很多经过很多人咀嚼的二手资料更贴近算法的“底层”，因为你很难了解到你参考的二手资料作者的知识水平，再一个就是任何分析题解都是以自己的思考角度分析的，很难与读者的角度契合，总归要回归原始的。