题目的主要信息：

• 给定一个元素非降序的、有重复数字的整型数组 nums 和一个目标值 target
• 找到第一个目标值的下标
• 如果找不到返回-1
• 进阶要求：时间复杂度$O(lo{g}_{2}n)O(log\_2n)$ ，空间复杂度$O(1)O(1)$

方法一：遍历查找

具体做法：

遍历数组，查找到第一个与目标值相等的数组元素，返回其下标。

class Solution {
public:
    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(n)$，遍历一次数组
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：二分法

具体做法：

既然数组是升序，可以使用二分法，从数组首尾开始，每次比较中点值，因为要找到第一个出现的目标值，因此中点值大于等于目标值区间右界都要向左边走，只有中点值小于目标左界才能往右，知道左右界相遇，此时检查右界下标的元素值是否等于目标，如果等则找到，否则找不到。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        if(nums.size() == 0) //先查空数组
            return -1;
        while(l < r){ //从数组首尾开始，直到二者相遇
            int m = (l + r) / 2; //每次检查中点的值
            if(nums[m] >= target) //要找到第一个目标值，因此大于等于等要朝左边走
                r = m;
            else 
                l = m + 1;
        }
        return nums[r] == target ? r : -1; //检查有无找到
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，对长度为$nn$的数组进行二分，最坏情况就是取2的对数
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：STL二分查找

具体做法：

可以直接调用STL的库函数lower_bound进行二分查找，它会直接返回数组中第一个目标的迭代器，不过查找前要检查数组是否为空。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) //空数组找不到
            return -1;
        auto iter = lower_bound(nums.begin(), nums.end(), target); //二分查找函数
        if(*iter != target)
            return -1; //没找到
        return iter - nums.begin(); //返回下标
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$， lower_bound的时间复杂度
• 空间复杂度：$O(1)O(1)$，无额外空间