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

题目描述

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

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

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

解题思路：

class Solution { public int[] searchRange(int[] nums, int target) { int[] res = new int[]{-1,-1}; int left = 0; int right = nums.length-1; while(left <= right){ int temp = (left + right) >> 1; if(nums[temp] > target){ right = temp - 1; }else if(nums[temp] < target){ left = temp + 1; }else{ left = temp; right = temp; while((right <nums.length-1)&&(nums[right] == nums[right+1])){ right++; } while((left > 0)&&(nums[left] == nums[left-1])){ left--; } res[0] = left; res[1] = right; } } return res; } }

这是最朴素的思想，二分查找，如果找到了再往两边拓展，处理边界条件，只可惜超时了。

需要对二分法再进行二分查找。

官方题解：

class Solution { public int[] searchRange(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } }