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

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

    如果数组中不存在目标值 target，返回 [-1, -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. 0 <= nums.length <= 105
    2. -109 <= nums[i] <= 109
    3. nums 是一个非递减数组
    4. -109 <= target <= 109
    1. class Solution {
    2.     public int[] searchRange(int[] nums, int target) {
    3.         /**
    4.         思路1:暴力法
    5.         （1）直接遍历数组，记录第一个等于目标元素的值
    6.         （2）记录第一个等于目标元素的位置，以及最后一个等于目标元素的值（
    7.         可以找到第一个大于的，做减一操作）
    8.         思路2：二分法
    9.         （1）定义两个指针，left,right，以及一个mid指针
    10.         （2）判断left+right / 2对应位置的数值是否大于target，如果大于那么right = mid
    11.         （3）如果小于，那么left = mid
    12.         （4）有个问题：如果找到了等于的index，此时有可能左右都有相等的元素，所以此时还不是最终的结果
    13.         （5）对4的一个优化，可以再执行一次二分，直到找到
    14.         （6）最终优化：因为要找的是两个位置，找到第一个相等的位置之后，再往两边遍历很可能出现o(n)的时间复杂度，所以做两次二分，分别找到第一个小于target的值，第一个大于target的值。
    15.         （7）找到以后，再对找到的两个坐标进行校验，是否在数组的长度范围内，是否left小于right，校验通过，返回这两个坐标，校验不通过，则直接返回-1,-1;
    16.          */
    17.         int length = nums.length;
    18.         if (length <= 0) return new int[]{-1,-1};
    19.         int left = binerySearch(nums,target,true);
    20.         // 右边界找到的是第一个大于taeget的位置，所以要减1
    21.         int right = binerySearch(nums,target,false) - 1;
    22.         // 判断要返回什么值，当left小于等于rigth，并且两个位置的值等于target，并且right位置小于数组长度
    23.         if(left<=right && right<length && nums[left]==target && nums[right]==target){
    24.             return new int[]{left,right};
    25.         }
    26.         return new int[]{-1,-1};
    28.     }
    29.     public int binerySearch(int[] nums,int target,boolean positionFlage){
    30.         // 细节：**********
    31.         // ans要初始值要设置为length，因为数组长度等于1的时候，返回的left会是-1,right会是0
    32.         // *************
    33.         int left=0,right = nums.length-1,ans = nums.length;
    34.         while (left<=right){
    35.             // 判断当前mid位置的值是否大于target值
    36.             int mid = (left + right) / 2;
    37.             // 如果大于，就设置mid-1为下一个范围的右边界
    38.             // 后置判断条件儿，代表的是找左边界还是右边界
    39.             // 如果是true，说明找的是左边界，如果是false，说明找的是右边界
    40.             // 原因是，true的时候，如果mid位置大于等于目标值，那么就会进入循环，移动右边界，
    41.             // 也就是一直会找到第一个小于target的位置
    42.             // 如果是false的时候，positionFlage && nums[mid]>= target始终不成立，
    43.             // 而else分之里面，只要是找到的位置小于等于目标值，就会一直移动左边界，
    44.             // 也就是会一直找到第一个大于target的位置
    45.             if(nums[mid] > target || (positionFlage && nums[mid]>= target)){
    46.                 right = mid-1;
    47.                 ans = mid;
    48.             }else{// 如果小于等于就设置mid为下一个范围的左边界
    49.             // 因为设置的是小于等于的时候才移动左边界，所以，一直能找到最右边的那个target的位置
    50.                 left = mid+1;
    51.             }
    52.         }
    53.         return ans;
    54.     }
    55. }