老师麻烦帮忙看一下LeetCode上704题

老师麻烦帮忙看一下LeetCode上704题

我用二分查找法,本地执行通过了,提交后报栈溢出的错。

http://img1.sycdn.imooc.com//climg/60edad1c090032c818490844.jpg

下面是我的代码:

/**
* @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)
}
}



正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

1回答
liuyubobobo 2021-07-14 03:09:03

如果 arr[min] 不是答案,往右找是在 [min + 1, r] 的区间找(你的代码没有问题);往左找是在 [l, min - 1] 的区间找(你的代码有问题)。


你的程序之所以会栈溢出是因为陷入无穷递归。为什么陷入死循环?你可以尝试调试跟踪一下在 [0, 2, 4] 中寻找 3,看看为什么你的程序没有终止?然后,再仔细理解一下课程中介绍的二分搜索的循环不变量,包括这个函数的语义是什么(这非常非常重要。)


继续加油!:)

  • 提问者 慕九州3950989 #1

    好的,谢谢老师讲解

    2021-07-14 09:40:23
  • 提问者 慕九州3950989 #2

    这个程序没有终止的原因是递归调用的时候每次都要比上一次的数据范围要小,而我代码当k<arr[min]时递归调用

    binarySearch(arr, k, l, min)

    的数据范围并没缩小,所以改成

    binarySearch(arr, k, l, min-1)

    这样就可以了。

    这个问题反应了我对这个算法的循环不变量理解有误。循环不变量应该为arr[l,min-1]<arr[min];arr[min+1,r]>arr[min]。每次递归都应维持这个循环不变量,而我上面的程序维持的是arr[l,min]<arr[min];arr[min+1,r]>arr[min]。再次感谢老师讲解?

    2021-07-14 10:03:07
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2589    人
  • 解答问题       1090    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师