【算法】数组查找之二分查找

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

二分查找

要求

有序
无重复元素

题目

模板

模板一

区间是[left,right],条件是left<=right

public int search(int[] nums, int target) {  
    //不需要判特  
    int left=0;  
    int right=nums.length-1;//right取 长度-1  
    while(left<=right){//条件是<=,因为当left=right的时候是有意义的  
        int middle=left+(right-left)/2;//防止溢出 ,left+right 不一定能保证 <= MAX_VALUE
        if(nums[middle]==target){  
            return middle;  
        }else if(nums[middle]>target){  
            right=middle-1;  
        }else{  
            left=middle+1;  
        }  
    }  
    return -1;//没有匹配结果  
}

未查询到结果查询结束时的状态
right+1=left

模板二

区间是[left,right),条件是left<right

public int search(int[] nums, int target) {  
    //不需要判特  
    int left=0;  
    int right=nums.length;//right取 长度-1  
    while(left<right){//条件是<=,因为当left=right的时候是有意义的  
        int middle=left+(right-left)/2;//防止溢出  
        if(nums[middle]==target){  
            return middle;  
        }else if(nums[middle]>target){  
            right=middle;  
        }else{  
            left=middle+1;  
        }  
    }  
    return -1;//没有匹配结果  
}

时间复杂度

O(n)=logn

假使总共有n个元素那么二分后每次查找的区间大小就是nn/2n/4…n/2^k接下来操作元素的剩余个数其中k就是循环的次数。
最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素
令n/2^k=1
可得k=log2n,是以2为底n的对数所以时间复杂度可以表示O(n)=O(logn).

参考资料https://blog.csdn.net/ShelleyLittlehero/article/details/80739884

查找目标

有时候查找目标不单纯是一个值可能需要提炼出一个表达式
例如https://leetcode.cn/problems/sqrtx/
要找的目标就是·middle * middle <= x

public int mySqrt(int x) {
        int ans = 0;//
        // 查找一个数 ans*ans=x
        // 查找一个整数 ans*ans<=x ans取满足这个条件的最大整数
        // 范围是[0,x]
        // 采用二分查找法
        int left = 0;
        int right = x;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if ((long) middle * middle <= x) {//注意转换成long
                ans = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return ans;


    }