在排列数组中查找元素的第一个位置和最后一个位置（二分法实现）

题目

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

注意： 1、你的算法时间复杂度必须是 O(log n) 级别； 2、如果数组中不存在目标值，返回 [-1, -1]。

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

注意点

1、数组有序，且算法时间复杂度必须是 O(log n) ，所以使用二分法； 2、使用二分法时要注意边界的考虑，和是否查找了所有元素；

使用了left = 0、right = nums.length - 1，则循环条件必须为left <= right，因为left和right都必须取到 [left, right]，所以当left = right时还需要继续判断；使用了left = 0、right = nums.length，则循环条件必须为left < right，因为left必须取到，而right不用取到 [left, right)，所以当left = right时不需要继续判断。

3、获取目标元素的边界时，当nums[mid] == target时，求左边界，压缩right；求右边界，压缩left。

实现

public int[] searchRange(int[] nums, int target) { if(nums == null) return new int[]{-1, -1}; if(nums.length == 1) return nums[0] == target ? new int[]{0, 0} : new int[]{-1, -1}; int[] result = new int[]{-1, -1}; int left = 0; int right = nums.length - 1; int mid = -1; while(left <= right){ mid = left + (right - left) / 2; if(nums[mid] == target){ //存在目标元素，直接退出循环 break; }else if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; } } //存在目标元素，获取左边界和右边界 if(mid != -1 && nums[mid] == target){ result[0] = searchLeftBound(nums, 0, mid, target); result[1] = searchRightBound(nums, mid, nums.length - 1, target); return result; } return result; } //已知存在目标元素，寻找目标元素的左边界 public int searchLeftBound(int[] nums, int left, int right, int target){ while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target){ //当中间位置的点等于target时，压缩右边界 right = mid - 1; }else if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; } } return right + 1; } //已知存在目标元素，寻找目标元素的右边界 public int searchRightBound(int[] nums, int left, int right, int target){ while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target){ //当中间位置的点等于target时，压缩左边界 left = mid + 1; }else if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; } } return left - 1; }