含平台段的双调数组最小值查找问题咨询

嘿，我来帮你解决这个二分查找处理平台段的问题！

你的原代码在遇到连续相等的元素（平台段）时会“卡壳”，核心问题是当arr[mid] == arr[right]时，你没法直接判断最小值在左半区还是右半区，原代码直接把right设为mid的逻辑会在某些场景下错误地排除掉最小值所在的区间（比如[2,2,2,1,2]这种情况，原代码会错误返回0而不是3）。

修正思路 #

我们需要调整二分的判断逻辑，针对相等的情况做特殊处理：

• 当arr[mid] > arr[right]：说明最小值肯定在mid右侧，把left移到mid+1；
• 当arr[mid] < arr[right]：说明最小值在mid或左侧，把right移到mid；
• 当arr[mid] == arr[right]：因为arr[right]和arr[mid]值相同，我们可以安全地把right减1来缩小范围——毕竟mid位置还保留着相同的值，不会错过最小值。

修正后的代码 #

#include <vector>
#include <cstddef>
#include <stdexcept>

size_t findMinIndex(const std::vector<int>& arr) {
    if (arr.empty()) {
        throw std::invalid_argument("Array cannot be empty");
    }
    
    size_t left = 0;
    size_t right = arr.size() - 1;
    
    while (left < right) {
        const size_t mid = left + (right - left) / 2;
        
        if (arr[mid] > arr[right]) {
            // 最小值在mid右侧，直接跳过左半区
            left = mid + 1;
        } else if (arr[mid] < arr[right]) {
            // 最小值在mid或左侧，保留mid继续查找
            right = mid;
        } else {
            // 相等时缩小右边界，避免误判区间
            right--;
        }
    }
    // 循环结束时left == right，就是最小值的位置
    return left;
}

测试验证 #

拿你给出的问题输入[4,3,3,2,1,2]测试：

1. 初始left=0, right=5，mid=2，arr[mid]=3 > arr[right]=2 → left=3；
2. left=3, right=5，mid=4，arr[mid]=1 < arr[right]=2 → right=4；
3. left=3, right=4，mid=3，arr[mid]=2 > arr[right]=1 → left=4；
4. 循环结束，返回4，对应最小值1，完全正确。

再测试极端平台场景[2,2,2,1,2]，最终会返回3，精准定位到最小值。

关于时间复杂度 #

最坏情况下（比如全数组元素相同），时间复杂度会退化为O(n)，但对于大多数存在有效分段的场景，依然保持O(logn)的效率。如果必须严格保证O(logn)，需要更复杂的分支处理，但这个方案在工程上已经足够简洁高效。

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