DX's Digital Garden

4.搜索旋转排序数组

2 min read

  • 3.18

    • 用 mid 与左右边界比，来判断左右哪个有序
    • 小循环里判断是否在里面，不在里面跑另一边继续循环

  • 2.14

    • mid《target《r
class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid]==target) return mid;
            if(nums[l]<=nums[mid]){
                if(nums[l]<=target&&target<=nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }else{
                if(target>=nums[mid]&&target<=nums[r]){
                    l = mid+1;
                }else{
                    r= mid-1;
                }
            }
        }
        return -1;
    }
}

  • 1.31

    • 外判断是哪边有序，里层判断是 target 在哪半边

  • 1.20

    • 蠢人灵机一动了
    • 虽然题目是值互不相同，但是边界是可能和 target 值相等的，所以判断都为等于号

  • 11.17

    • 正常的二分法
      • 多了一个外层嵌套
      • 先进入有序的一侧,看target在不在,如果不在,那就缩小到另一个无序的一侧
      • 在进入另一侧后,在开始判断上一步(有点递归的意思)
class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target) return mid;
            if(nums[left]<=nums[mid]){
                //左边有序
                if(nums[left]<=target&&target<=nums[mid]){
                    //target在左边
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }else{
                //右边有序
                if(nums[mid]<=target&&target<=nums[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
        }
        return -1;
    }
}
  • 先判断左边是有序的还是右边是有序的
  • 在判断其中有序的一段中,target在左边还是右边

Graph View