在先非递增后非递减数组中高效查找最小值的解决方案咨询

你描述的是典型的单谷数组（先非递增后非递减的数组）的最小值查找场景，目前已经有成熟的O(logn)时间复杂度的二分查找实现，效率远优于O(n)的遍历方案。

核心二分逻辑 #

利用数组左右两段的单调性差异，通过中间值和相邻值的比较收缩查找范围：

• 若arr[mid] > arr[mid+1]：说明当前mid处于左侧非递增区间，最小值一定在mid右侧，更新左边界left = mid + 1
• 若arr[mid] <= arr[mid+1]：说明当前mid处于右侧非递减区间，最小值一定在mid或mid左侧，更新右边界right = mid
• 循环直到left == right，此时arr[left]就是数组最小值

C++实现代码 #

int findMinVal(const std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2; // 避免整数溢出
        if (arr[mid] > arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return arr[left];
}

覆盖场景说明 #

该实现可以兼容所有符合特征的数组场景：

• 常规V型数组（即你给出的示例场景）
• 全非递增数组（最小值在末尾）
• 全非递减数组（最小值在开头）
• 数组长度为1、长度为2的极端场景

以你给出的示例{90, 80, 70, 60, 55, 62, 71, 89, 104}测试，最终会定位到下标为4的位置，返回值为55，符合预期。

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