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

二分查找到目标值然后左右找到坐标

问题在于：找左右坐标的时候时间复杂度不是O(logN)

class Solution {public int[] searchRange(int[] nums, int target) {int[] ans = {-1, -1};if (nums.length == 0) return ans;int l = 0, r = nums.length;while (l < r) {int m = (l + r) / 2;if (nums[m] == target) {ans[0] = m; ans[1] = m;int tempm = m;while (m > 0 && nums[m - 1] == target) {ans[0] = --m;}while (tempm < nums.length - 1 && nums[tempm + 1] == target) {ans[1] = ++tempm;}break;} else if (nums[m] < target) {l = m + 1;} else {r = m;}}return ans;}
}

之前提到过二分查找不仅可找到相等的数值，更关键的是它可以将数组分为截然不同的两种情况，因此我们可以借助这个性质找到第一个大于等于target的值（左下标）和第一个大于target的值（右下标需要-1）（两次二分查找）

找到第一个>=x的值和找到第一个>x的值见：

2258. 逃离火灾（附：二分查找的理解）

class Solution {public int[] searchRange(int[] nums, int target) {int[] ans = {-1, -1};if (nums.length == 0) return ans;int lIndex = func(0, nums.length, nums, target);int rIndex = func(0, nums.length, nums, target + 1) - 1;if (lIndex <= rIndex) ans = new int[] {lIndex, rIndex};return ans;}public int func(int l, int r, int[] nums, int x) {int res = -1;// 找到第一个大于等于x的下标（left）// 大于等于target正常使用// 大于target相当于大于（target + 1）while (l < r) {int m = (l + r) / 2;if (nums[m] < x) {l = m + 1;} else {r = m;}}res = l;return res;}
}