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

题目描述：

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

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

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

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

思路1：

1、二分法先找到右边界；
    1、设定左右指针left = 0和right=len-1，找到中间数num[min]
    2、比较目标值与num[min]的大小，大于目标值则修改右指针right = mid - 1;
    3、小于目标值则修改左指针 left = mid + 1;
    4、等于目标值，则判断是否该指针是最后一个，或者是否下一个数比目标值大，如果都不是，如是，则ans[1] = mid;如否，则修改左指针left = mid + 1；
2、二分法再找到左边界；
    1、设定左右指针left = 0和right=ans[1]，找到中间数num[min]
    2、比较目标值与num[min]的大小，大于目标值则修改右指针right = mid - 1;
    3、小于目标值则修改左指针 left = mid + 1;
    4、等于目标值，则判断是否该指针是第一个，或者是否前一个数比目标值小，如是，则ans[0] = mid;如否，则修改左指针right = mid - 1;
3、最终返回结果ans；

Java解法：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if(len ==0 || nums[0] > target || nums[len - 1] < target){
            return new int[]{-1, -1};
        }
        int left = 0;
        int right = len - 1;
        int[] ans = new int[]{-1, -1};
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }else if(nums[mid] < target)
            {
                left = mid + 1;
            }else {
                if (mid == len - 1 || nums[mid + 1] > target)
                {
                    ans[1] = mid;
                    break;
                }else
                {
                    left = mid + 1;
                }
            }
        }
        left = 0;
        right = ans[1];
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }else if(nums[mid] < target)
            {
                left = mid + 1;
            }else {
                if (mid == 0 || nums[mid - 1] < target)
                {
                    ans[0] = mid;
                    break;
                }else
                {
                    right = mid - 1;
                }
            }
        }
        return ans;
    }
}

python3解法：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array