[数据结构与算法]【C++二分查找详解】分类and框架

一、寻找一个数（基本二分查找）

1、题目描述

????????给定单调不减有序数组 nums ，寻找 target 是否在数组中，若找到返回其下标，否则返回-1。

2、代码框架

/*基本二分*/
int binarySearch(vector<int>& nums,int target)
{
    int left=0,right=nums.size()-1;
    int mid;
    while(left<=right)
    {
        mid=(right-left)/2+left;//防止了 left 和 right 太大直接相加导致溢出。
        if(nums[mid]>target) right=mid-1;
        else if(nums[mid]<target) left=mid+1;
        else return mid;
    }
    return -1;
}

3、细节分析（仅针对上述代码）

（1）为什么 while 循环中的条件为 <= 而不是 < ？

? ? ? ? 上述代码 right=nums.size()-1 ，搜索区间为 [left,right] 左闭右闭。

????????当未搜索到给定 target 时，跳出循环的条件为 left==right+1 ，此时搜索区间变为 [right+1,right] ，区间为空，表示给定的数组已全部搜索完毕。

? ? ? ? 若 while 循环中条件变为 < ，跳出循环的条件为 left==right?，此时搜索区间变为 [right,right] ，此时循环已跳出， right 这个值却未被考虑在内，故会出错。

（2）此算法有什么缺陷？

????????比如说给你有序数组?[1,2,2,2,3]?，?target?为 2，此算法返回的索引是 2，没错。但是如果我想得到?target?的左侧边界，即索引 1，或者我想得到?target?的右侧边界，即索引 3，这样的话此算法是无法处理的。

二、寻找左侧边界的二分搜索

1、题目描述

????????给定单调不减有序数组 nums ，寻找 target 是否在数组中，若找到返回其左侧边界的下标，否则返回-1。

2、代码框架

/*寻找左边界二分*/
int binarySearchLeft(vector<int>& nums,int target)
{
    int left=0,right=nums.size();//改变①
    int mid;
    while(left<right)//改变②
    {
        mid=(right-left)/2+left;//防止了 left 和 right 太大直接相加导致溢出。
        if(nums[mid]>target) right=mid; //改变③
        else if(nums[mid]<target) left=mid+1;
        else right=mid;//改变④
    }
    //改变⑤
    if(left==nums.size()) return -1;
    return (nums[left]==target)? left:-1;
}

3、细节分析（仅针对上述代码）

（1）为什么 while 循环中的条件变为 < ？

????????因为?right=nums.size() ,因此每次循环的搜索区间是 [left,right)左闭右开。while(left<right)?终止的条件是?left==right?，此时搜索区间?[left,left)?为空，所以可以正确终止。（改变①②）

（2）为什么?left=mid+1?，?right=mid?和之前的算法不一样？

????????因为搜索区间是?[left,right)?左闭右开，所以当?nums[mid]?被检测之后，下一步的搜索区间应该去掉?mid?分割成两个区间，即?[left,mid)?或?[mid+1,right)?。（改变③）

（3）为什么该算法能够搜索左侧边界？

????????关键在对于?nums[mid]==target?这种情况的处理，找到 target 时不要立即返回，而是缩小搜索区间的上界?right?，在区间?[left,mid)?中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。（改变④）

（4）如何处理?nums?中不存在?target 这种情况？

????????针对[2,3,5,7]?target=1 or 8 这两种情况，可以看出，?left?变量的取值区间是闭区间[0, nums.size()]。利用改变⑤即可处理。

?

?三、寻找右侧边界的二分搜索

1、题目描述

????????给定单调不减有序数组 nums ，寻找 target 是否在数组中，若找到返回其右侧边界的下标，否则返回-1。

2、代码框架

/*寻找右边界二分*/
int binarySearchRight(vector<int>& nums,int target)
{
    int left=0,right=nums.size();
    int mid;
    while(left<right)
    {
        mid=(right-left)/2+left;//防止了 left 和 right 太大直接相加导致溢出。
        if(nums[mid]>target) right=mid;
        else if(nums[mid]<target) left=mid+1;
        else left=mid+1;//改变①
    }
    //改变②
    if(right==0) return -1;
    return (nums[right-1]==target)? (right-1):-1;
}

3、细节分析（仅针对上述代码）

（1）为什么这个算法能够找到右侧边界？

? ? ? ???关键在对于?nums[mid]==target?这种情况的处理，找到 target 时不要立即返回，而是缩小搜索区间的下界 left?，在区间?[mid+1,right)?中继续搜索，即不断向右收缩，达到锁定右侧边界的目的。（改变①）（2）

（2）如何处理?nums?中不存在?target 这种情况？

???????left?变量的取值区间是闭区间[0, nums.size()]。利用改变②即可处理。

（3）为什么最后返回 right-1?而不像左侧边界的函数，返回?right?？

? ? ? ??为什么要减一，这是搜索右侧边界的一个特殊点，在?nums[mid]==target 时 left=mid+1 ，即对?left?的更新必须是?left=mid+1?，就是说 while 循环结束时，?nums[left]?一定不等于?target?了，而?nums[left-1]?可能是?target 。同时while 循环结束时 right=left ，为了体现是右边界搜索故把 left 替换成 right。

?