题解 | #二分查找-II#

NC105 二分查找-II

1. 顺序查找

思路略。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @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;
    }
};

• 时间复杂度：对于长度为n的数组，时间复杂度为O(n), 因为做了一轮循环
• 空间复杂度：O(1)

2. 二分查找

既然题目叫二分查找，那么本题的关键点肯定是要考察二分查找。

能用二分查找的依据是题目中存在单调性，本题中数组的顺序是升序的，满足要求。二分查找的关键点有以下几步：

• 确定目标值：nums 中的第一个出现的target
• 确定边界范围：第一个i满足 num[i]==target, 且 前面的i均是num[i] < target.

这道题跟很多其他的二分稍有不同的是，其他的二分答案、二分搜索题如果满足f(mid)==target，其中f是某个关于mid的单调函数，可以直接得到mid即为答案，而本题却只能判断出mid右侧不符合题意，所以在大于小于等于三种情况下，均需要调整上下界，而利用l<r作为递归出口。

分别以样例1和2为例，使用一张图来描述二分查找过程：

实现如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @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) {
            // 这里不可以写上取整，否则在l+1==r的情况下会陷入死循环
            int mid = (l+r)>>1;
            // 如果大于目标值，说明mid及其右侧都不可能是答案
            if (nums[mid] > target) r = mid-1;
            // 如果小于目标值，说明mid及其左侧都不可能是答案
            else if (nums[mid] < target) l = mid+1;
            // 如果等于目标值，说明mid右侧不是答案，但mid有可能是！！！！！！
            else r = mid;
        }

        // 请注意这里wa了一次，需要特判断下数组是否为空，如果为空会越界
        if (nums.size() && nums[l] == target) return l;

        // 如果没找到目标值，是-1
        return -1;
    }
};

• 时间复杂度：O(logn), 标准的二分查找
• 空间复杂度：O(1), 未定义数组