二分查找-II（二分）

题意

在有序数组中,找目标值首次出现的位置.

思路分析

找大于等于目标值的值

而数组是有序的,可以二分找大于等于目标值的值

对于找大于等于目标值的值,可以用lower_bound

找准确的值

既然能通过二分找到首个大于等于目标值的值

那么如果这个值和目标值相等,则输出下标

如果不等,则不存在,因为它是首个大于等于目标值的值

边界处理

有一种情况是,目标值大于整个数组,所以还要考虑下标超界

题目样例

以题目样例[1,2,4,4,5],4为例,如果是手动二分,则下标变化如图

如果最后搜的和值不等则输出-1

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        int i = lower_bound(nums.begin(),nums.end(),target) - nums.begin(); // 二分找到下标
        return i == nums.size() || nums[i] != target ? -1: i; // 判断超界限和不等于
    }
};

复杂度分析

空间复杂度: 只用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

时间复杂度: 用了二分查找值,所以时间复杂度为$O(log(n))O(log(n))$