如何用最少探针查找具有重心特性的隐藏数值列表最小值？

这问题挺有意思的，本质是在一个单谷数组（也就是V型数组，最小值为谷点，向两侧递增）里找最小值，最优解法是用变种二分查找，能把探测次数降到O(log n)级别，比线性遍历高效太多。

核心思路 #

先明确数组的核心特性：

• 谷点（最小值位置）左侧的元素，从左到右是递减的（因为越靠近谷点数值越小）
• 谷点右侧的元素，从左到右是递增的（越远离谷点数值越大）
• 谷点本身是数组的最小值，比左右相邻元素都小（如果谷点不在数组首尾）

基于这个特性，我们可以通过二分法不断缩小查找范围，每次只需要探测1-2个位置的数值就能判断方向。

具体步骤 #

假设数组长度为n，位置索引从0开始（用1-based也完全没问题，逻辑一致）：

1. 初始化左右边界：left = 0，right = n - 1
2. 当left < right时，重复以下操作：
   • 计算中间位置：mid = (left + right) // 2
   • 探测mid和mid + 1位置的数值（记为val_mid和val_mid_next）
   • 如果val_mid > val_mid_next：说明谷点在mid右侧（当前还处于递减区间），更新left = mid + 1
   • 如果val_mid < val_mid_next：说明谷点在mid或其左侧（当前处于递增区间，或mid就是谷点），更新right = mid
3. 当left == right时，这个位置就是谷点，探测该位置的数值即为最小值

示例演示（用你给出的数组） #

你的数组是：[3397, 3343, 3297, 3251, 3215, 3159, 3107, 3061, 3029, 2979, 2939, 2879, 2829, 2781, 2733, 2673, 2615, 2579, 2633, 2669, 2713]（长度21，0-based谷点在索引17）

• 初始left=0，right=20
• 第一次：mid=10，探测得val_mid=2939，val_mid_next=2879 → 2939>2879，更新left=11
• 第二次：mid=(11+20)//2=15，探测得val_mid=2673，val_mid_next=2615 → 2673>2615，更新left=16
• 第三次：mid=(16+20)//2=18，探测得val_mid=2633，val_mid_next=2669 → 2633<2669，更新right=18
• 第四次：mid=(16+18)//2=17，探测得val_mid=2579，val_mid_next=2633 → 2579<2633，更新right=17
• 第五次：left=16，right=17，mid=16，探测得val_mid=2615，val_mid_next=2579 → 2615>2579，更新left=17
• 此时left=right=17，探测该位置得数值2579，即为最小值

整个过程一共探测了10次，要是优化边界判断（比如当mid是最后一个元素时只探测mid），还能再减少1-2次，比线性遍历的21次少太多。

边界情况处理 #

• 如果数组只有1个元素：直接探测该位置即可
• 如果谷点在数组首位：比如数组是[1,2,3,4,5]，第一次探测mid=2，val_mid=3 < val_mid_next=4，更新right=2，继续缩小范围直到left=right=0
• 如果谷点在数组末尾：比如数组是[5,4,3,2,1]，第一次探测mid=2，val_mid=3 > val_mid_next=2，更新left=3，继续缩小直到left=right=4

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