老师麻烦帮忙看一下LeetCode上704题
我用二分查找法,本地执行通过了,提交后报栈溢出的错。
下面是我的代码:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
return binarySearch(nums,target,0,nums.length-1);
};
var binarySearch = function(arr,k,l,r){
// 递归退出的条件
if(l>r){
return -1
}
// 中间索引
let min = Math.floor(l + (r - l) / 2 );
if (arr[min] === k) {
return min;
} else if (k > arr[min]) {
return binarySearch(arr, k, min + 1, r);
} else {
return binarySearch(arr, k, l, min)
}
}
14
收起
正在回答 回答被采纳积分+1
1回答
liuyubobobo
2021-07-14 03:09:03
如果 arr[min] 不是答案,往右找是在 [min + 1, r] 的区间找(你的代码没有问题);往左找是在 [l, min - 1] 的区间找(你的代码有问题)。
你的程序之所以会栈溢出是因为陷入无穷递归。为什么陷入死循环?你可以尝试调试跟踪一下在 [0, 2, 4] 中寻找 3,看看为什么你的程序没有终止?然后,再仔细理解一下课程中介绍的二分搜索的循环不变量,包括这个函数的语义是什么(这非常非常重要。)
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星