Dx's Tech Notes

5._搜索旋转排序数组中的最小值

2 min read

  • 3.18

  • 整体逻辑都对

  • 返回的是具体的数，而不是下标

  • 2.14

    • 依旧忘了，mid 与 nums【mid】
    • 返回 left 就是结果

  • 1.31

    • 这里是缩边界，且 right=mid 所以循环条件不能等于，避免死循环
特性标准二分 (找 target)找最小值/峰值 (找边界)
循环条件left <= rightleft < right
Right 更新right = mid - 1 (排除 mid)right = mid (保留 mid)
Left 更新left = mid + 1left = mid + 1
终止状态区间为空 (left > right)区间剩一个 (left == right)
返回值mid 或 -1nums[left]

  • 1.20

    • 判断 mid 在左悬崖还是右悬崖
    • 左悬崖需要 left = mid+1；右悬崖（nums【mid】《=nums【right】）需要 rigth = mid，因为 mid 可能为最小值

  • 11.17

     mid    right
     ↓        ↓
[ 5, 6, 7, 1, 2 ]
           ↑ 最小值
  • 如果nums[mid]>nums[right],则mid肯定不是最小值,而是在mid的左侧,所以left = mid+1
  • 如果nums[mid]⇐nums[right],则一定时升序的,那么mid有可能是最小值,但是不确定所以right=mid,把mid包括在内
  • yysy,已老实,这里都是mid和right做对比,跟left没关系(在对比阶段)
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length-1;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]>nums[right]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
}
  • 判断最小值在哪边<
  • 如果在右边则right=mid;
  • 结束条件left = right
条件说明操作
nums[mid] > nums[right]最小值在右边left = mid + 1
nums[mid] < nums[right]最小值在左边（含 mid）right = mid

Graph View