二分查找到目标值然后左右找到坐标
问题在于:找左右坐标的时候时间复杂度不是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
的值见:文章来源:https://www.toymoban.com/news/detail-813929.html
2258. 逃离火灾(附:二分查找的理解)文章来源地址https://www.toymoban.com/news/detail-813929.html
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;
}
}
到了这里,关于34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!