数组（一）：二分法

二分法是在排序后的数组中查找给定值，从而将O(n)的查找复杂度降低为O(logn)。根据条件的不同，二分法共有四种情况：

• 在非重复数组中可以找到给定值
• 在重复数组中可以找到给定值
• 在非重复数组中无法找到给定值
• 在重复数组中无法找到给定值

一、非重复数组中可以找到给定值（初始模板）

使用双闭环区间来进行二分查找，这里一共有两个注意点：

• 查找退出条件为left <= right
• 中间值计算使用left + (right - left) / 2，放置计算left + right发生越界

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){   //注意点1
            int middle = left + (right - left) / 2;  //注意点2
            if(nums[middle] > target) right = middle - 1;
            else if(nums[middle] < target) left = middle + 1;
            else return middle;
        }
        return -1;
    }
};

二、重复数组中可以找到给定值

在重复数组中，使用初始模板只能找到任意一个给定值的下标。

1、重复数组中可以找到第一个给定值下标和最后一个给定值下标

相较于初始模板，在重复数组中可以找到给定值时，查找数组中的第一个给定值和最后一个给定值的下标需要做如下改动：

• 对于查找第一个给定值，在nums[middle] == target的情况下仍更新右边界，退出时left即为第一个给定值的下标
• 对于查找最后一个给定值，在nums[middle] == target的情况下仍更新左边界即可，退出时候right即为最后一个给定值下标

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int startIndex = 0;
        int endIndex = 0;
        /---查找数组中第一个给定值的下标---/
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int middle = left + (right - left) / 2;
            if(nums[middle] >= target) right = middle - 1;
            else left = middle + 1;
        }
        startIndex = left;

		/---查找数组中最后一个给定值的下标---/
        left = 0;
        right = nums.size() - 1;
        while(left <= right){
            int middle = left + (right - left) / 2;
            if(nums[middle] <= target) left = middle + 1;
            else right = middle - 1;
        }
        endIndex = right;
        if(startIndex <= endIndex) return {startIndex, endIndex};
        return {-1, -1};
    }
};

三&四、在非重复数组中无法找到给定值&在重复数组中无法找到给定值

无论是重复数组还是非重复数组，如果数组中没有目标值，那么我们使用二分法查找时最后会因为left <= right不满足而退出，此时left和right满足：

• left为数组中第一个大于目标值的元素下标；如果有多个相同该元素，left指向第一个
• right为数组中第一个小于目标值的元素下标；如果有多个相同该元素，right指向最后一个
  
• 特别注意这里left是小于目标值，right是大于目标值，别记反了

五、二分法库函数

在C++中algorithm头文件中，存在三个二分法函数lower_bound、upper_bound和binary_search，这三个函数对于重复数组和非重复数组均适用。

1、lower_bound

• 使用格式为lower_bound( begin,end,num)

在从小到大排序的数组中，begin和end是数组的两个迭代器，lower_bound使用二分法查找第一个大于或等于num的元素，返回指向该元素的迭代器。通过解引用才能获得该元素，或者减去迭代器begin才能获得该元素在数组中的下标。如果找不到这样的元素则返回尾后迭代器end()

vector<int> nums{1,2,5,6,8,9};
/通过解引用获得数组中第一个大于或等于4的元素值
cout << *lower_bound(nums.begin(), nums.end(), 4) << endl;
/通过减去开始位置的迭代器获得数组中第一个大于或等于4的元素的下标
cout << lower_bound(nums.begin(), nums.end(), 4) - nums.begin() << endl;

2、upper_bound

• 使用格式为upper_bound( begin,end,num)

在从小到大排序的数组中，begin和end是数组的两个迭代器，upper_bound使用二分法查找第一个大于num的元素，返回指向该元素的迭代器。通过解引用才能获得该元素，或者减去迭代器begin才能获得该元素在数组中的下标。如果找不到这样的元素则返回尾后迭代器end()

3、binary_search

• 使用格式为binary_search(begin, end, num)

在从小到大排序的数组中，begin和end是数组的两个迭代器，upper_bound使用二分法查找数组中是否存在于num相等的元素，如果存在，返回true，否则返回false

3、lower_bound、upper_bound与binary_search在从大到小排序数组中的使用

使用greater<type>()使算法适用于从大到小排序，其本质是重载运算符

lower_bound( begin,end,num,greater<type>()) 
//type为数组元素类型（一般为int），返回第一个小于等于num的元素迭代器

upper_bound( begin,end,num,greater<type>()) 
//type为数组元素类型（一般为int），返回第一个小于num的元素迭代器

binary_search( begin,end,num,greater<type>()) 
//在从大到小排序数组中寻找是否存在于num相等的元素，存在则返回true，否则返回false

错误警示

1、把数组下标当成元素去和目标值比较

习题

704,367,34,35,69