在排序数组中查找元素的第一个和最后一个位置
来源：3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
慕粉3884565
2020-08-27
就是下面是我的代码，我写的有问题
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let middle = parseInt((left + right) / 2)
if (target > nums[middle]) {
left = middle + 1
} else if (target == nums[middle]) {
let num = nums[middle]
let last = middle
if(right-left==0){
return [0,0]
}
for (let j = middle; j < right; j++) {
if (num == nums[j]) {
last = j;
}
}
return [left, last]
} else {
right = middle - 1
}
}
return [-1, -1]
};
感觉是自己代码有问题恳请老师指导
写回答
1回答
-
liuyubobobo
2020-08-29
你的 while 循环的条件是错的，要想确定一个元素，应该是 while(left <= right)，请再看一下这个课程的 3-1 和 3-2。
但是修改完这一点，你的程序依然是错的。关键在于中间 else if (target == nums[middle]) 中间找左右边界是错误的。Leetcode 会给出错误的 case，实际用这个 case 去调试一下，看看自己的代码为什么得到了错误的结果？
另外，你的这个思路，其实是 O(n) 级别的算法。因为中间 else if (target == nums[middle]) 部分的逻辑是线性的。这个问题可以在 O(logn) 的时间里解决。你需要使用二分查找法，找到 >= 某个元素的最小值，就是左边界；找到 > 某个元素的最小值，这个最小值左边的元素，就是右边界。
对此，Leetcode 上这个专题应该有介绍：https://leetcode-cn.com/leetbook/detail/binary-search/，可以参考。
继续加油！：）
00
相似问题