https://blog.csdn.net/2601_95366422/article/details/158771447上节课链接一.题目153. 寻找旋转排序数组中的最小值 - 力扣LeetCode二.思路讲解第一步找二分性题目给出的数组原本是升序排列经过若干次旋转后变成了由两段升序子数组拼接而成的形式前一段的所有元素都大于后一段的所有元素除非旋转次数为数组元素个数的倍数即整个数组仍然是升序。这种结构天然具备二分性我们可以通过比较中间元素与数组最右边的元素来判断中间元素位于前一段还是后一段从而确定最小值所在的区间。即使数组完全升序即没有旋转也可以看作后一段为空此时最小值就是第一个元素。因此无论是否旋转数组都满足“可以通过比较缩小范围”的条件从而可以使用二分查找。第二步采用左端点还是右端点我们要找的是数组中的最小值。在旋转数组中最小值就是后一段的第一个元素也就是第一个小于等于最右边元素的元素因为后一段所有元素都小于前一段且后一段本身是升序。因此我们需要找到第一个满足“小于等于最右边元素”的位置这正是左端点二分查找的典型应用。采用左端点模板中点取向下取整缩进规则为当中间值大于最右边元素时说明中间值在前一段最小值在右边left mid 1否则中间值小于等于最右边元素说明中间值在后一段或就是最小值right mid。循环结束时left即为最小值的索引。第三步为什么选择最右边的元素作为基准值选择数组最右边的元素作为基准值是因为它位于数组末尾且具有明确的特性在旋转数组中最右边的元素一定是后一段的最后一个元素如果数组没有旋转它就是整个数组的最大值。通过比较中间值与最右边元素可以准确判断中间值属于哪一段如果nums[mid] nums[right]其中right指向最右边说明中间值在前一段因为前一段所有元素都大于后一段那么最小值一定在mid的右侧。如果nums[mid] nums[right]说明中间值在后一段包括可能的最小值那么最小值在mid左侧或就是mid本身。 这种比较方式简单有效且能统一处理旋转和未旋转的情况。如果选择最左边的元素作为基准则需要考虑更多边界情况因此最右边的元素是更优的选择。三.代码演示class Solution { public: int findMin(vectorint nums) { int left 0; int n nums.size(); int right n - 1; int x nums[right]; while(left right) { int mid left (right - left) /2; if(nums[mid] x) left mid 1; else right mid; } return nums[left]; } };四.代码讲解一、循环条件与中点计算采用while (left right)作为循环条件而不是left right。这是因为当左右指针相遇时区间内只剩一个元素此时无需继续二分可以直接在循环外返回该元素。这种写法可以避免死循环并符合左端点模板的常规写法。中点计算采用向下取整的公式即mid left (right - left) / 2。当区间长度为偶数时中点会偏向左边这确保了当left和right相邻时中点指向left从而保证区间能够正确收缩不会出现right原地不动的情况。向下取整是左端点查找的精髓也是避免死循环的关键。二、区间缩进规则在循环中使用x nums[right]作为基准值即数组最右边的元素。根据nums[mid]与x的比较结果按照以下规则更新指针当nums[mid] x时说明mid位于前一段旋转后较大的那一段因为前一段的所有元素都大于后一段而最小值在后一段。因此最小值一定在mid的右侧可以安全地将左指针移动到mid 1即舍弃左半区间。当nums[mid] x时说明mid位于后一段包括可能的最小值因为后一段的所有元素都小于等于最右边元素且后一段本身升序。此时最小值可能在mid左侧也可能就是mid本身。因此将右指针移动到mid保留mid在搜索区间内继续向左寻找。注意这里不能用right mid - 1因为mid有可能是最小值必须保留。三、循环结束后的处理循环结束时left与right相等此时指向的位置就是数组中最小值的索引。直接返回nums[left]即可无需额外判断。无论数组是否经过旋转这个结果都是正确的。四、细节注意基准值x取nums[right]即数组最右边的元素它在循环中保持不变因为right会更新但x是初始最右边元素的值。循环中比较的是nums[mid]与固定的x因此需要确保x的值在循环过程中始终代表原始最右边元素这是合理的。由于数组元素互不相同不存在相等干扰比较逻辑清晰。