二分查找

使用二分查找的前提条件:

  • 有序(单调递增或递减)

  • 存在边界

  • 能够通过索引访问

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法,前提是数据结构必须先排好序,可以在数据规模的对数时间复杂度内完成查找。但是,二分查找要求线性表具有有随机访问的特点(例如数组),也要求线性表能够根据中间元素的特点推测它两侧元素的性质,以达到缩减问题规模的效果。

代码模板:

public int sort(int[] nums, int target){
    int left = 0;
    int right = nums.length-1;
    while(left < right){
        int mid = (left+right)/2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
}

例题1:

LeetCode ——69.x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4 输出: 2 示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

class Solution {
    public int mySqrt(int x) {
        
        if (x==0 || x==1) return x;
        
        int left = 0;
        int right = x/2+1;
        int res = 0;
        while(left <= right){
            int mid = (left + right)/2;
            if(mid == x/mid){
                return mid;
            }else if(mid < x/mid){  //取小,防止过大
                left = mid +1;
                res = mid;
            }else{
                right = mid -1;
            }
        }
        return res;
    }
}

例题2:

剑指offer 53 - II 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例 1:

输入: [0,1,3] 输出: 2 示例 2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

解法一:个人套模板解法

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0]==0 ?1:0;
        if(nums[len-1]== len-1) return len;
        if(nums[0]!=0) return 0;

        int left = 0;
        int right = len -1;
        int mid = 0;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid]>mid && nums[mid-1]==mid-1){
                return mid;
            }else if(nums[mid] == mid ){
                left = mid + 1;
            }else if(nums[mid]>mid){
                right = mid - 1;
            }
        }
        return mid;
    }
}

执行结果:(内存消耗更少)

image-20210201105645806

解法2:网上大佬的解法(代码更简洁)

class Solution {
    public int missingNumber(int[] nums) {

        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid] == mid)  left = mid +1;
            else right = mid -1;
        }
        return left;
    }
}

执行结果:

image-20210201105459759

以上是我个人学习总结的笔记,当然目前还是还是不够的,对于二分法的理解还要多刷题,多思考,多理解!

end

评论