鲁迅曾说，笑傲江湖其实讲的就是最真实的人性，有些人明明做了坏事，却能装出一副正义凛然的样子，有些人明明做了好事，却被人说成是坏人。这就是江湖，这就是人性。如果你想不被人欺负，就要学会自强自立，不依赖别人。对于程序员来说，笔试想要取得好成绩，多刷一点 LeetCode 也是应该的。

题意

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

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

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

难度

中等

示例

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

分析 1

在排序数组中查找元素的第一个和最后一个位置，如果不考虑时间复杂度的话，会非常简单。

第一次遍历，从左到右找到第一个等于 target 的元素，记录下它的位置；第二次遍历，从右到左找到第一个等于 target 的元素，记录下它的位置，最后返回这两个位置即可。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lef = -1,rig = -1;
        // 找第一个位置
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == target){
                lef = i;
                break;
            }
        }
        // 找最后一个位置
        for(int i = nums.length - 1;i >= 0;i--){
            if(nums[i] == target){
                rig = i;
                break;
            }
        }
        return new int[]{lef,rig};
    }
}

这样的速度也是出奇的快，直接击败 100% 的 Java 用户，这样的结果，只能证明，要么 LeetCode 的测试用例不够严谨；要么就是，暴力算法也并没有想象中那么差，不仅效率高，代码还简单。

分析 2

当然了，题目要求的时间复杂度为 O(log n)，那么我们还是需要使用二分查找的。

怎么去使用二分查找法呢？

一开始，我们可能会想到直接查找数组中是否存在这个target值，然后再向左右扩展，可是这个思路如果遇到nums = [5,5,5,5,5], target = 5的情况，就需要遍历整个数组！

这时候，时间复杂度就又变成了$O(n)$，而不是$O(\log{n})$。

怎么办呢？

如果用C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，upper_bound()会返回大于 target 的第一个元素。

但我们毕竟是 Java 选手，Java 有这样类似的方法吗？

我能想到的是Arrays.binarySearch()，但该方法只负责找到一个，并不区