二分查找到目標(biāo)值然后左右找到坐標(biāo)
問題在于：找左右坐標(biāo)的時(shí)候時(shí)間復(fù)雜度不是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;
}
}
之前提到過二分查找不僅可找到相等的數(shù)值，更關(guān)鍵的是它可以將數(shù)組分為截然不同的兩種情況，因此我們可以借助這個(gè)性質(zhì)找到第一個(gè)大于等于target的值（左下標(biāo)）和第一個(gè)大于target的值（右下標(biāo)需要-1）（兩次二分查找）
找到第一個(gè)>=x的值和找到第一個(gè)>x的值見：文章來源：http://www.zghlxwxcb.cn/news/detail-813929.html
2258. 逃離火災(zāi)（附：二分查找的理解）文章來源地址http://www.zghlxwxcb.cn/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;
// 找到第一個(gè)大于等于x的下標(biāo)（left）
// 大于等于target正常使用
// 大于target相當(dāng)于大于（target + 1）
while (l < r) {
int m = (l + r) / 2;
if (nums[m] < x) {
l = m + 1;
} else {
r = m;
}
}
res = l;
return res;
}
}
到了這里，關(guān)于34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（二分查找）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
