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

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

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

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

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

解题思路：
如何查找元素在数组中的开始位置？
只需要在while中，即使nums[i]==target时，也将right = mid - 1。这样循环结束后的left就是第一个大于等于target的位置，如果等于target，则是target在数组中的开始位置；如果不等于target，则说明数组中没有target。（在插入问题中，此时的left则是target的插入位置）。

那么同理，如何查找元素在数组中的结束位置呢？
只需要在while中，即使nums[i]==target时，也将left= mid + 1。这样循环结束时的right就是最后一个小于等于target的位置。

如果没有target的开始位置，说明数组中没有这个元素，自然也就不必再找结束位置了，可以提前返回答案。

class Solution {public int[] searchRange(int[] nums, int target) {int n = nums.length;int left = 0, right = n - 1;int first = 0, last = 0;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}if (left < n && nums[left] == target) {first = left;} else {// 不存在target，直接返回return new int[]{-1, -1};}left = 0;right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}}// 前面已经判断存在target，那么就肯定存在最后一个位置，不用再判断right合法性last = right;return new int[]{first, last};}
}

优化：
其实我们在找结束位置时，可以不用新的二分查找逻辑，我们只需要复用查找开始位置的二分查找逻辑即可，只不过我们查找的不再是target的开始位置，而是target+1的开始位置，我们找到了target+1的开始位置，那么该位置的前一个位置自然就是target的结束位置了。

class Solution {public int[] searchRange(int[] nums, int target) {int first = binSearch(nums, target);if(first == nums.length || nums[first] != target){return new int[]{-1, -1};}int last = binSearch(nums, target + 1) - 1;return new int[]{first, last};}private int binSearch(int[] nums, int target){int left = 0, right = nums.length - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return left;}
}