为何查找排序旋转数组最小值的二分函数对纯升序数组返回正确结果

问题描述 #

• 需求：查找元素互不相同的排序后旋转数组中的最小元素
• 实现逻辑：基于二分查找拆分搜索区间，通过比较区间中点mid和两端点low/high的大小关系收敛搜索范围，核心假设是最小值一定位于数组的拐点位置（即前一个元素大于后一个元素的位置）。
• 异常现象：代码逻辑中没有显式处理「当前子区间完全有序（未旋转）」的分支，理论上应该无法正确返回全升序数组的最小值，但实际传入完全升序数组[1,2,3,4,5,6,7,8,9]时，函数正确返回了最小值1。最初猜测可能是寄存器残留值碰巧命中正确结果，但通过g++逐行调试始终未定位到具体原因。

问题代码 #

核心函数实现：

// Function to find the minimum element in sorted and rotated array.
int minNumber(int arr[], int low, int high)
{
    int mid = (low + high) / 2;

    if (low > high)
        return -1;

    if (low == high)
        return arr[low];

    if (mid == 0 || arr[mid - 1] > arr[mid])
        return arr[mid];
    else if (arr[mid] > arr[high])
    {
        return (minNumber(arr, mid + 1, high));
    }
    else if (arr[mid] < arr[low])
    {
        return (minNumber(arr, low, mid - 1));
    }
}

完整可运行测试代码：

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends

class Solution
{
public:
    // Function to find the minimum element in sorted and rotated array.
    int minNumber(int arr[], int low, int high)
    {
        int mid = (low + high) / 2;

        if (low > high)
            return -1;

        if (low == high)
            return arr[low];

        if (mid == 0 || arr[mid - 1] > arr[mid])
            return arr[mid];
        else if (arr[mid] > arr[high])
        {
            return (minNumber(arr, mid + 1, high));
        }
        else if (arr[mid] < arr[low])
        {
            return (minNumber(arr, low, mid - 1));
        }
    }
};

// { Driver Code Starts.

int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        Solution obj;
        cout << obj.minNumber(a, 0, n - 1) << endl;
    }
    return 0;
} // } Driver Code Ends

根因分析 #

这段代码返回正确结果完全是未定义行为导致的巧合，并非逻辑正确：

1. 当处理完全升序的数组/子区间时，一定满足arr[low] <= arr[mid] <= arr[high]，此时两个else if分支的条件都不成立，函数不会进入任何递归调用，也没有对应的return语句。
2. 在C++标准中，控制流到达非void函数的末尾且没有执行return语句属于未定义行为，程序的返回值完全取决于当前编译环境、调用约定下寄存器/栈内存的残留值：在x86平台的System V调用约定中，int类型返回值存储在eax寄存器中，测试时刚好该寄存器残留了数组首元素（即最小值1）的值，才会输出正确结果。
3. 这种巧合不具备可移植性：更换编译选项（比如开启O2优化）、更换运行平台、调整数组成员，都可能得到完全错误的返回值，甚至直接触发程序崩溃。

修复方案 #

只需要补充完全有序区间的处理分支即可：当arr[mid] <= arr[high]且arr[mid] >= arr[low]时，说明当前区间已经是升序状态，最小值就是区间左端点arr[low]，直接返回即可：

int minNumber(int arr[], int low, int high)
{
    int mid = (low + high) / 2;

    if (low > high)
        return -1;

    if (low == high)
        return arr[low];

    if (mid == 0 || arr[mid - 1] > arr[mid])
        return arr[mid];
    else if (arr[mid] > arr[high])
    {
        return (minNumber(arr, mid + 1, high));
    }
    else if (arr[mid] < arr[low])
    {
        return (minNumber(arr, low, mid - 1));
    }
    // 补充完全有序区间的返回逻辑
    return arr[low];
}

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