【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置

本节博客主要是通过“在排序数组中查找元素的第一个和最后一个位置”总结关于二分算法的左右界代码模板，有需要借鉴即可。

1.题目

题目链接：LINK

这个题要求我们求这个排序数组的一个元素的开始位置与结束位置。

可以用暴力求解的方法，把第一次出现的数字下标记录一下，最后一次记录一下，返回结果，除了复杂度差之外没什么不好的。

当然我们这里说一下二分算法的思想。之所以可以使用二分算法，这是因为该数组是有序的，可以利用二分算法的“二段性”将其分割。

用两次二分算法：

• 一方面，我们可以将整个数组分为大于等于t和小于t来找left点
  
• 另一方面，我们可以将整个数组分为大于t和小于等于t来找right点
  

但是这里有一些代码细节值得注意！！！

2.二分边界算法

2.1查找区间左端点

思考：我们在寻找左端点时候为什么要对数组按照小于t和大于等于t进行划分？

答：关键是因为我们要找左端点，左端点一定不可能在小于t的区间里。

通过上面的图片可知，我们要想找到一个数的左端点，那么这个左端点(我们要寻找的点)一定不再大于t这个区域，所以我们可知

• mid < ret时，left = mid + 1
• mid >= ret时，right = mid

2.1.1循环条件

while(left < right)//... √
while(left <= right)//... ×

循环条件选：left < right

这里为什么不是left <= right 呢？

• left==right的情况下，即是最后结果，无需进行重复判断。
• 可能有些情况下会出现死循环问题
  下面是对上面两个理由进行论证：
  在所有可能情况中，无非存在三种情况，
• ①left与right中间存在要找的ret点
  
  此时，mid = ret,mid == right,那么left = mid，会不断进入循环，陷入死循环。
• ②left与right中间所有点全部大于我们要找的右端点
  
  到了最后，mid > ret, mid = right，right = mid，会存在死循环问题
• ③left与right中间所有点全部小于我们要找的右端点
  
  mid < ret,left = mid + 1,不会出现死循环问题。

2.1.2求中点的操作

我们求中点无非两种求法

①mid = left + (right - left) / 2; √
②mid = left + (right - left + 1) / 2; ×

这俩主要区别就是在数字个数是偶数情况下，①式取靠左的中点；②式取靠右的中点。

然后对于查找区间右端点而言，必须选用①式。

为什么，下面来进行解释？

如果选用②式，会存在下面情况：比如，mid指向right，然后mid所在的值>=ret值，就会不断死循环

注：if mid >= ret,right = mid;

2.1.3总结

在求目标值左端点时候，第一循环条件不能有等于，第二是求中点要用靠右中点。

2.2查找区间右端点

通过上面的图片可知，我们要想找到一个数的左端点，那么这个右端点(我们要寻找的点)一定不再大于t这个区域，所以我们可知

• mid <= ret时，left = mid
• mid > ret时，right = mid - 1

2.1.1循环条件

while(left < right)//... ×
while(left <= right)//... √

循环条件选：left < right

这里为什么不是left <= right 呢？

• left==right的情况下，即是最后结果，无需进行重复判断。
• 可能有些情况下会出现死循环问题

下面是对上面两个理由进行论证：

在所有可能情况中，无非存在三种情况，

• ①left与right中间存在要找的ret点
  
  此时，mid = ret,mid == right,那么right = mid，会不断进入循环，陷入死循环。
• ②left与right中间所有点全部大于我们要找的右端点
  
  到了最后，mid > ret,mid == right，right = mid - 1，不会出现死循环问题
• ③left与right中间所有点全部小于我们要找的右端点
  
  mid < ret,left = mid,此时会出现死循环问题。

2.1.2求中点的操作

我们求中点无非两种求法

①mid = left + (right - left) / 2; ×
②mid = left + (right - left + 1) / 2; √

这俩主要区别就是在数字个数是偶数情况下，①式取靠左的中点；②式取靠右的中点。

然后对于查找区间右端点而言，必须选用②式。

为什么，下面来进行解释？

如果选用①式，会存在下面情况：比如，mid指向left，然后mid所在的值<=ret值，left = mid,如此就会不断死循环

注：if mid <= ret,left = mid;

2.1.3总结

在求目标值右端点时候，第一循环条件不能有等于，第二是求中点要用靠右中点。

2.3总结

找左端点：

• mid < ret时，left = mid + 1
• mid >= ret时，right = mid

while(left < right)//...
mid = left + (right - left) / 2;

找右端点：

• mid <= ret时，left = mid
• mid > ret时，right = mid - 1

while(left < right)//...
mid = left + (right - left + 1) / 2;

根据上面的算法总结我们可以解决上面题目

3.参考解题代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> ret;
        //处理特殊情况
        if(nums.size() == 0)
        {
            ret.push_back(-1);
            ret.push_back(-1);
            return ret;
        }
        int left = 0, right = nums.size() - 1;
        //处理左端点
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        if(nums[left] == nums[right] && nums[left] == target)
        {
            ret.push_back(left);
        }
        else
        {
            ret.push_back(-1);
        }
        //处理右端点
        left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid;
            }
        }
        if(nums[left] == nums[right] && nums[right] == target)
        {
            ret.push_back(right);
        }
        else
        {
            ret.push_back(-1);
        }
        return ret;
    }
};

4.模板总结

5.总结

这个题目我感觉掌握了二分边界代码原理其实不难，重点肯定是那个二分边界算法原理，需要自己多理解一下。

EOF