二分法

力扣题目连接：二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例一：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路

二分查找是一个比较简单的算法，其前提条件为：

• 数组内元素是有序的
• 数组中元素不能重复，一旦重复就无法找到唯一下标了

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间（接下来要查找的范围）的定义一般为两种，左闭右闭即[left, right]（right也在查找范围内，结果可能是right），或者左闭右开即[left, right)（right不在查找范围内，最终结果不可能是right）。

[left, right]图示以及代码

因为区间为[left, right]，这里要注意：

• while(left<=right)，这里left可以等于right，因为left和right都是查找区间的一部分，所以两者相等说明只有一个查找元素了，这是有意义的。
• if(nums[middle] > target),说明target在middle左边，因为当前这个nums[middle]一定不是target，这时要将查找区间右边界right改为middle-1。if(nums[middle] < target)同理，应当将left改为middle+1.

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

• 时间复杂度：O(log2 n) 因为二分法每次都查找一半（即1/2）
• 空间复杂度：O(1) 空间复杂度为常数

[left, right）图示以及代码

因为区间为[left, right]，这里要注意：

• while(left < right)，这里left不能等于right，因为right不是查找区间的一部分，所以当left和right相等时说明查找区间内没有数组元素内容了，这没有意义。
• if(nums[middle] > target),说明target在middle左边，因为当前这个nums[middle]一定不是target，而有边界right是取不到的，所以将查找区间右边界right改为middle就可以。但是如果if(nums[middle] < target)，应当将left改为middle+1，因为left仍是查找区间的一部分。

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

• 时间复杂度：O(log2 n) 因为二分法每次都查找一半（即1/2）
• 空间复杂度：O(1) 空间复杂度为常数