二分查找实战：旋转数组最小值与点名问题

二分查找实战：旋转数组最小值与点名问题

二分查找不仅仅是简单的折半搜索，关键在于找到合适的判断标准，将查找区间一分为二。下面通过两道经典题目，深入剖析二分法在不同场景下的应用逻辑。

23. 寻找旋转排序数组中的最小值

题目描述： 已知一个长度为 n 的升序排列数组，在某个未知的下标 k 处进行了旋转（例如 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。请找出其中最小的元素。

解题思路

旋转后的数组可以看作由两个有序部分组成。虽然整体无序，但局部依然保留了单调性。我们可以利用这种特性来缩小搜索范围。

核心在于比较中间元素 mid 与边界值的关系：

• 如果 nums[mid] >= nums[0]，说明 mid 位于左半部分（较大值区域），最小值一定在右侧，因此更新 left = mid + 1。
• 如果 nums[mid] < nums[0]，说明 mid 位于右半部分（较小值区域），最小值可能是 mid 或者在左侧，因此更新 right = mid。

当 left == right 时，指针指向的元素即为最小值。此外，若数组本身未发生旋转（即 nums[0] <= nums[n-1]），直接返回首元素即可。

参考实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        // 如果数组没有旋转，第一个元素就是最小值
        if (nums[0] <= nums[n - 1]) {
            return nums[0];
        }

        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 中点值大于等于首元素，说明在左半段，最小值在右边
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                // 否则在右半段，最小值在左边或就是 mid
                right = mid;
            }
        }
         nums[left];
    }
};