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

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

思路

进行一次二分查找，如果查到了，那么再接一个while循环走到当前重复数字的左端点，后接一个while循环走到右端点；如果没有查到返回一个{-1，-1}即可。
具体见代码注释。

复杂度

• 时间复杂度: $O(logn)$
• 空间复杂度: $O(1)$

Code

class Solution {public int[] searchRange(int[] nums, int target) {if (nums.length == 0) return new int[]{-1, -1};int left = 0, right = nums.length - 1;int mid = 0;while (left <= right) {mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}//这个情况是查找到的刚好不在区间内，在外部，例如{2,2} target=3//此时 left = 2if (left < 0 || left > nums.length - 1 || nums[left] != target) {return new int[]{-1, -1};}//找到左端点的下标，要判断是否是左边界while ((left - 1) > 0 && nums[left - 1] == target) left--;int[] result = new int[2];result[0] = left;//找到右端点的下标，要判断是否是右边界while ((left + 1) <= nums.length - 1 && nums[left + 1] == target) left++;result[1] = left;return result;}
}