【二分查找】力扣 34. 在排序数组中查找元素的第一个和最后一个位置

一、题目

二、思路

将题目转化为求解 target 和 target + 1 的查找。分别采用最基础的二分查找即可。

三、题解

class Solution {public int[] searchRange(int[] nums, int target) {int n = nums.length;int start = lowerBound(nums, target);if (start == n || nums[start] != target) {return new int[] {-1, -1};}// start 找到了，end 也一定存在，因此 end 无需检验int end = lowerBound(nums, target + 1) - 1;return new int[] {start, end};}/* 寻找大于等于 target 的第一个数，若存在 target 返回 left，即为第一个 target 的位置若有序数组中都是小于 target 的数，left 一直右移，最后 left = n，返回left，即为数组长度，tips: 返回的 left 不在下标范围内若有序数组中都是大于 target 的数，right 一直左移，left始终没有移动，最后 left = 0，tips: 返回的 left 在下标范围内，但所指向的数值与 target 不同*/public int lowerBound(int[] nums, int target) {int n = nums.length;int left = 0, right = n - 1;while (left <= right) { // 区间不为空int mid = left + (right - left)/ 2; // java 防止溢出if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;// 最后结束时，right 在 left左边一个位置，right + 1 = left// left - 1 永远指向的是红色，right + 1 永远指向的是蓝色，left的位置就是要找}
}