hot100之二分查找，

hot100之二分查找，

搜索插入位置(035)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int lef = -1;
        int rig = n;
        while(lef+1 < rig){
            int mid = (lef + rig) / 2;
            if (nums[mid] < target){
                lef = mid;
            }else rig = mid;
        }
        return rig;
    }
}

• 分析

基础二分

搜索二维矩阵(074)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int lef = -1;
        int rig = m*n;
        while (lef+1 < rig){
            int mid = (lef + rig) / 2;
            int x = matrix[mid/n][mid%n];

            if (x < target) lef = mid;
            else if (x > target) rig = mid;
            else return true;
        }
        return false;
    }
}

• 分析

把每一个row 横向相连, 作二分

在排序数组中查找元素的第一个和最后一个位置(034)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int start = searchLower(-1 ,nums, target);
        if (start == nums.length || nums[start] != target) return new int[]{-1,-1};

        int end = searchLower(start, nums, target+1) -1;
        return new int[] {start, end};
    }

    private int searchLower(int lef, int[] nums, int target){

        int rig = nums.length;

        while (lef + 1 < rig){
            int mid = (lef + rig) / 2;
            if (nums[mid] < target) lef = mid;
            else rig = mid;
        }

        return rig;
    }
}

• 分析

通过两次二分 查找 target 和target+1的起始位置, 确定target的范围

搜索旋转排序数组(033)

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length -1;
        int lef = -1;
        int rig = n;
        while (lef + 1< rig){
            int mid = (lef + rig) / 2;
            if (check(nums, target, mid)){       //target在mid右侧
                lef = mid;
            }else rig = mid;
        }
        return nums[rig] == target ? rig : -1;
    }

    private boolean check(int[] nums, int target, int idx){    
        int x = nums[idx];
        int end = nums[nums.length-1];

        if (x < end){
            return x < target && target <= end;  // mid在小端 且比target小
        }
        // mid在大端 且< target在小端 || target > mid >
        return x < target || target <= end; 
    }
}

• 分析

通过mid和end值的对比, 确定mid的位置<旋转小端, 旋转大端>

根据 mid的位置再分类讨论

寻找旋转排序数组的最小值(153)

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int lef = -1;
        int rig = n;
        while (lef+1 < rig){
            int mid = (lef + rig) / 2;
            if(nums[mid] > nums[n-1]){   // 在右侧
                lef = mid;
            }else rig = mid;
        }
        return nums[rig];
    }
}

• 分析

判断 mid 在<大端, 小端> →<右移, 左移>

• 感悟

二分用来查找数据的拐点, 以<条件>作check()

寻找两个正序数组的中位数(004)

这题给我写晕厥了

相关文章

• hot100之回溯下，
• hot100之回溯上，
• hot100之图论，
• hot100之二叉树下，
• hot100之二叉树上，