34. 在排序数组中查找元素的第一个和最后一个位置（二分查找）

34. 在排序数组中查找元素的第一个和最后一个位置

• 题目
• 解题思路
• 代码

题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是O(log n)级别。

如果数组中不存在目标值，返回 [-1, -1]。

解题思路

这题一看到“你的算法时间复杂度必须是 O(log n) 级别。”就知道应该用二分查找，本题的难点不是找到target，而是找到target后还要判断找到的target的前后是否还有别的target，因为题目求的是target的起始和结束位置。具体思路没啥好说的，就在代码注释一看就懂了
说起来就很难顶，自己写了一个多小时，结果发现还是有几种情况考虑不到，最后还是看了答案。我真粪🐷！

代码

class Solution {
       public int[] searchRange(int[] nums, int target) {
        int find = searchRangeHelper(nums, target);
        //如果没找到，返回{-1, -1}
        if (find == -1){
            return new int[]{-1, -1};
        }

        int left = find - 1;
        int right = find + 1;
        //查看前面是否还有target
        while (left >= 0 && nums[left] == target) {
            left--;
        }
        //查看后面是否还有target
        while (right < nums.length && nums[right] == target) {
            right++;
        }

        /*
        简单理解，假如只有一个target，那么我们开始为了查找是否还有别的target而让left-1，right+1了，
        这时候却没有搜索到别的target，那么我们应该给left+1，right-1，来让它恢复原来的大小，再返回。
         */
        return new int[]{left + 1, right - 1};
    }

    //二分法查找
    public int searchRangeHelper(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
                /*找到了该目标值的地址，就将地址返回，但是要注意，再寻找一下还有没有其余的target，
                因为可能有多个target，但是题目要求的是target的起始、结束位置，比如[1,1,1,1]
                 */
            }
        }
        return -1;//如果没找到就返回-1
    }
}