二分查找法实例应用的细节分析

细节二：

搜索时选定新边界，新边界的值是mid ± 1还是mid

在进行一次搜索判断之后，查找新边界时，新边界一般有两种选择（以right为例）

• right = mid - 1
• right = mid

按照标准的二分查找框架，这两种赋值方式的区别是新区间是否还要包括mid这个点。

一般来说选择新边界时，其实已经对mid这个值已经判断过了，秉持着最大程度地缩小搜索区间的理念，按理说应该要将mid这个点在新区间排除掉的；

但联系上一个问题，如果判断条件是left < right，那么搜索区间是左闭右开区间，即使right = mid，也不会判断mid；但是如果right = mid - 1，那么就会少判断right = mid - 1这个点，所以这里新区间的边界为right = mid。

所以这里的缩小区间表示式是和判断条件联系在一起的，需要考虑实际情况，然后再进行判断

尽管二分查找有统一的框架模板，操作步骤；但二分查找不是一种框架模板，而是一种思想

案例

1. 当数组中含有多个目标数字

• 查找最左边目标数字的索引
• 查找最右边目标数字的索引

2. 当数组中不含有目标数字

• • 查找目标数字的插入位置

搜索边界

集合中含有多个符合要求的解，查找左边界或者右边界

e.g.

• 按照全闭区间查找查找左右边界的关键是nums[mid] == target时，如何划定新区间。

如果查找左边界：

int binarySearch(vector<int>& nums,int target) { int n = nums.size(); int left = 0,right = n - 1; int ans = -1; while(left <= right){ int mid = left + (right - left) / 2; if (nums[mid] == target){ // 这里能判断出 mid 可能是左边界，但是对于 mid - 1 我们是无法判断的，所以 ans = mid; right = mid - 1; }else if (nums[mid] > target) { right = mid - 1; }else { left = mid + 1; } } return ans; }

最终结果都是ans。在每一次判断(nums[mid] == target)中，我们只能判断出mid是符合要求的，而无法判断出mid - 1或者mid + 1是否符合要求，所以ans = mid。

按照这个思路中，其实也可以不采用 ans 这个变量，而采用right + 1或者left - 1的形式，因为right + 1或者left - 1等于mid，不过这需要进一步判断right + 1或者left - 1是否在数组范围内

如果你将nums[mid] == target和nums[mid] > target或者nums[mid] < target合并起来，你还需要判断nums[left - 1]或者nums[right + 1]是否等于target，因为当nums[mid] > target或者nums[mid] < target时，也会给ans赋值。