题解 | #二分查找-I#

NC160 二分查找-I

题意

给你一个不重复、递增的数组nums，和目标值target，求target在nums中的下标，从0开始，如果不存在输出-1.

1. 暴力解法

直接遍历数组查找。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) 
                return i;
        }
        return -1;
    }
};

时间复杂度： $O(n)$ , 遍历一轮数组。
空间复杂度： $O(1)$ 常数个变量

2. 二分查找

二分查找适用于满足单调性的序列，每次可以把待查找区间收敛为原来的一半。二分查找（或者二分答案）的基本思路是：

确定上界和下界
确定中点和谁比较，要上取整还是下取整
如果大于、小于、等于待比较对象，（或者对于二分答案，f(mid)=true或false), 如何收敛区间（尤其需要注意边界，是否包含mid）

一般地，记住一个原则，每次对半分的时候尽量要求两边均匀。具体来说，如果收敛区间是l=mid+1,则mid需要下取整，如果是r=mid-1，则需要上取整。

用一个图来简述样例1的查找过程：
图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid; // 找到
            else if (nums[mid] > target) r = mid - 1; // 因为不重复，所以可以确信mid不是答案，右端点至少位于mid-1
            else l = mid + 1; // 同上
        }

        // 这里需要做一个边界判断，如果数组为空，nums[l]会触发段错误，统一返回-1
        if (nums.size()>0 && nums[l] == target) return l;
        else return -1;
    }
};

时间复杂度: $O(logn)$ , 每次区间收敛一半
空间复杂度: $O(1)$ . 常数个变量