二分查找实战：寻找旋转排序数组最小值与点名问题解析

前言

二分查找是算法面试中的高频考点，其核心在于利用数据的二段性快速缩小搜索范围。本文通过两道经典例题，演示如何构建判断条件，将时间复杂度优化至对数级别。

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

题目描述： 假设按照升序排序的数组在预先未知的某个点上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。请找出其中最小的元素。

解题思路： 这道题的关键在于识别旋转后的数组特性。虽然整体不再有序，但局部依然保持单调性。我们可以观察到，数组被分成了两个有序部分：

1. 前半部分：所有元素都大于等于最后一个元素。
2. 后半部分：所有元素都小于等于第一个元素。

最小值恰好位于这两个部分的交界处。利用这个性质，我们可以使用二分查找来定位它。

具体策略如下：

• 初始化左右指针 left 和 right。
• 计算中点 mid。
• 如果 nums[mid] >= nums[0]，说明 mid 落在前半部分，最小值一定在右侧，更新 left = mid + 1。
• 如果 nums[mid] < nums[0]，说明 mid 落在后半部分，最小值可能是 mid 或者在左侧，更新 right = mid。
• 当 left == right 时，即为最小值位置。

注意一个边界情况：如果数组本身没有旋转（即 nums[0] <= nums[n-1]），直接返回首元素即可。

C++ 代码实现：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        // 处理未旋转的情况
        if (nums[0] <= nums[n - 1]) {
            return nums[0];
        }
        
        int left = 0;
        int right = n - 1;
        
         (left < right) {
             mid = left + (right - left) / ;
            
             (nums[mid] >= nums[]) {
                left = mid + ;
            }  {
                right = mid;
            }
        }
         nums[left];
    }
};