线下面试的时候碰到了个这个题目，当时要求时间复杂度O(log(n))，想到了二分，但是由于存在重复元素，没想好具体的实现，今天研究了下。

题目描述

题目链接：LeetCode34 在排序数组中查找元素的第一个和最后一个占位置

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

解题思路

题目的目的是求出给定元素的第一次出现的位置和最后一次出现的位置，我们分两次二分查找即可。

先找第一次出现的位置，我们就利用普通的二分法查找，如果找不到，那就直接返回[-1,-1],否则找到了nums[mid] == target，那我们就改变右边界，因为我们的目的是找到最左边出现的target，那我们就往mid的左边找，right = mid - 1;并且记录first=mid保存第一次出现的位置。

再找第二次出现的位置，和上边一样，假如我们找到了target，这次的目的是找到最右边的target，那我们要想办法左边界，让左边界右移，left=mid+1并且记录last=mid保存最后一次出现的位置
最后返回[first,last]即可。

实现代码

//在排序数组中查找元素的第一个和最后一个位置，要求时间复杂度为O(logn)
public class LeetCode34 {
    public static int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int first = -1;
        int last = -1;
        if (nums.length == 0) {
            return new int[]{first, last};
        }
        //找第一个等于target的位置
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                first = mid;
                //由于这里是找第一个出现的，我们就往当前的左边继续找，更新右边界
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        //找第二个等于target的位置
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                last = mid;
                //由于这里是找最后一个出现target的位置，所以就往右边找，更新左边界
                left = mid + 1; //关键
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return new int[]{first, last};
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] ints = searchRange(nums, target);
        System.out.println(Arrays.toString(ints));
    }
}