老师麻烦帮忙看一下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){ 

// 递归退出的条件<br>     if(l>r){<br>            return -1<br>        }<br>        // 中间索引<br>        let min = Math.floor(l + (r - l) / 2 );<br>        if (arr[min] === k) {<br>            return min;<br>        } else if (k > arr[min]) {<br>            return binarySearch(arr, k, min + 1, r);<br>        } else {<br>            return binarySearch(arr, k, l, min)<br>        }<br>}<br><br>

慕九州3950989 2021-07-13

源自：二分查找法 1-2 二分查找法的递归写法

收起

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]时递归调用
1
binarySearch(arr, k, l, min) 
的数据范围并没缩小，所以改成
1
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