LeetCode 153寻找旋转排序数组最小值：移除优化行引发无限递归的测试用例

• 触发无限递归的核心数据集是长度为1的旋转排序数组，例如 [1]。

原因分析 #

当输入数组长度为1时，主函数会调用 findPivot(arr, 0, 0)，移除if(start==end) return arr[start];后，代码执行流程如下：

1. 条件arr[start]<arr[end]不成立（两个索引指向同一个元素，值相等）；
2. 条件end-start ==1不成立（索引差为0）；
3. 计算中间索引m=(0+0)/2=0；
4. 判断(m>0 && arr[start]<=arr[m-1]) && (arr[m]<=arr[arr.length-1])，因m=0，m>0为假，整体条件不成立；
5. 进入else分支，再次调用findPivot(arr, 0, 0)，形成无限递归循环。

补充说明 #

对于LeetCode 153题目中元素互不相同、长度大于1的旋转排序数组，移除该行后不会触发无限递归：

• 若数组未旋转（完全升序），arr[start]<arr[end]会直接返回最小值；
• 若数组已旋转，递归调用时会不断缩小搜索范围，最终触发end-start ==1的条件返回最小值，或找到分界点返回结果。

内容的提问来源于stack exchange，提问作者curiousengineer