旋转排序数组中Binary Search的疑问：首循环为何能定位最小值？

问题背景 #

给定原本升序排列、元素互不相同的整数数组nums，它可能在某个未知 pivot index 处旋转（例如[0,1,2,4,5,6,7]旋转后变为[4,5,6,7,0,1,2]）。给定旋转后的数组nums和目标值target，返回target在nums中的索引，若不存在则返回-1。

写出的代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0, r=nums.size()-1;
        
        while(l<r) {    // 疑问：数组非单调，为何能用二分查找？
            int m=l+(r-l)/2;
            if(nums[m]>nums[r]) l=m+1;
            else r=m;
        }
        
        // cout<<"Lowest at: "<<r<<"\n";
        if(nums[r]==target) return r;   //target==lowest number
        int start, end;
        if(target<=nums[nums.size()-1]) {
            start=r;
            end=nums.size()-1;
        } else {
            start=0;
            end=r;
        }
        l=start, r=end;
        while(l<r) {
            int m=l+(r-l)/2;
            if(nums[m]==target) return m;
            if(nums[m]>target) r=m;
            else l=m+1;
        }
        
        return nums[l]==target ? l : -1;
    }
};

核心疑问 #

1. 第一个while循环中数组并非单调，为何能应用Binary Search？
2. 是否是在抛物线结构中寻找最低点，或是求解凸函数的最小值？
3. 理解l、m、r的变化逻辑，但无法确定为何当nums[m]>nums[r]时，最小值一定在右侧。

解答 #

1. 为什么能用二分查找？ #

二分查找的核心要求不是整个数组完全单调，而是每次迭代能通过一个判断条件，把搜索范围精准缩小一半。这个旋转后的数组虽然整体不单调，但有个关键特性：它是由两个连续的升序子数组拼接而成，且左半段的所有元素都大于右半段的所有元素。基于这个特性，我们每次都能确定最小值所在的子区间，所以完全可以用二分查找。

2. 和抛物线/凸函数无关 #

这个数组的结构是分段单调的，不是抛物线或者凸函数。它就是两段独立的升序序列，最小值就是两段的分界点（旋转点），第一个循环的目标就是找到这个分界点。

3. 为什么nums[m]>nums[r]时最小值在右侧？ #

结合数组的分段特性分析：

• 如果nums[m] > nums[r]，说明m处于左边的升序子数组，r处于右边的升序子数组——因为左半段的所有元素都比右半段大。那最小值必然在m的右侧（也就是[m+1, r]区间），因为左半段的元素都比右半段的大，最小值肯定在右半段里。
• 如果nums[m] <= nums[r]，说明[m, r]这个子区间是完全升序的，最小值要么是nums[m]，要么在[l, m]区间里，所以把r设为m来缩小搜索范围。

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