题解 | #二分查找-II#

方法一：二分查找到指定元素后找到最左边
核心思想：
首先使用二分查找，寻找到一个与目标值相等的数，之后往左侧线性查找到最左边或到不等于目标值的元素
核心代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n < 1 || nums[0] > target || nums[n - 1] < target) {
            return -1; //数组为空，数组中所有元素都大于/小于目标值时，直接返回-1
        }
        int i = 0, j = n - 1, mid = 0;
        while(i <= j) {
            mid = (i + j) / 2;
            if(nums[mid] < target) {
                i = mid + 1;
            } else if(nums[mid] > target) {
                j = mid - 1;
            } else {
                //找到目标值，往左侧线性查找
                while(mid > 0 && nums[mid - 1] == target) {
                    --mid;
                }
                return mid;
            }
        }
        return -1;//找不到目标值
    }
};

复杂度分析：
时间复杂度：$O（n)$，最坏情况下，整个数组左侧都等于目标值，则相对于对数组进行线性遍历，需要O（n)时间
空间复杂度：$O（1）$，过程中只使用了常数个变量

方法二：优化的二分查找
核心思想：
方法一中，寻找到一个目标值后的方案是对左侧进行线性查找，这在最坏情况下可能导致$O（n)$的时间复杂度，可以对二分查找进行优化，保证往左侧逼近目标值。
具体解释：
当$nums[mid] < targe$t时，说明目标值绝对在mid右侧，此时可以令$i=mid+1$
当$nums[mid] = target$时，说明目标值可能为mid,也可能在mid左侧，此时可以令$j = mid$，保证不会丢失答案
当$nums[mid] > target$时，说明目标值绝对在mid左侧，此时可以令$j = mid - 1$
终止条件，因为当$i=j=target$时，$j$并不会步进，所以终止条件必须为$i<j$，在循环结束后再判断$nums[i]$是否等$target$决定答案值。

核心代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n < 1 || nums[0] > target || nums[n - 1] < target) {
            return -1; //数组为空，数组中所有元素都大于/小于目标值时，直接返回-1
        }
        int i = 0, j = n - 1, mid = 0;
        while(i < j) {
            mid = (i + j) / 2;
            if(nums[mid] < target) {
                i = mid + 1;
            } else if(nums[mid] > target) {
                j = mid - 1;
            } else {
                j = mid;//为避免丢失答案，不能为mid-1
            }
        }
        return nums[i] == target ? i : -1; //最后进行一次判断
    }
};

复杂度分析：
时间复杂度：$O（log(n)),$即为二分查找的复杂度,不会出现方法一中的最坏情况