当前位置：首页 > article >正文

【二分算法】模板总结

article 2024/11/14 21:15:49

一、二分查找时间复杂度

二、二分查找模板

2.1 模板一：标准的二分查找

2.2 模板二：二分查找左边界

2.3 模板三：二分查找右边界

三、总结：

一、二分查找时间复杂度

时间复杂度可以表示 O(n)=O(log2n)或者O(n)=O(logn)

二、二分查找模板

什么时候可能需要用二分查找？

（1）待查找的数组有序或者部分有序

（2）可以发现二段性

（3）题目要求时间复杂度低于 O(n)，或者直接要求时间复杂度为 O(log n)

2.1 模板一：标准的二分查找

适用场景：数组元素有序且不重复

public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<=right) {
            int mid = left + ((right-left)>>1);//+运算的优先级高
            if(target==nums[mid]) return mid;
            else if(nums[mid]<target) left = mid+1;
            else right = mid-1;
        }
        return -1;
    }

注意点：

（1）为什么 while 循环的条件是 <=，而不是 < ？

当元素只有一个且这个元素正好就是目标值，那么没有=就进入不了循环，得不到正确的结果

（2）计算 mid 时需要防止溢出

left + ((right -left) >> 1) 其实和 (left + right) / 2 是等价的，这样写的目的一个是为了防止 (left + right) 出现溢出，另外用位运算替代除法提升性能

2.2 模板二：二分查找左边界

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

注意点：

（1）为什么 while 循环的条件是 <，而不是 <= ？

left等于right的时候就已经得到了最终结果，如果判断了，就会进入死循环，因为right后面一直不动

（2） 求中点的操作

求左边界根标准模板一样，不用+1，直接left+（right-left）/2（总个数为偶数个时取中点的时候取左边那个

（3）为啥nums[mid]==target右边界也要变

要寻找左边界，当nums[mid] == target，这个mid的位置不一定就是最左侧的那个边界，所以还要继续收缩右边界

2.3 模板三：二分查找右边界

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

注意点：

（1）为什么 while 循环的条件是 <，而不是 <= ？

left等于right的时候就已经得到了最终结果，如果判断了，就会进入死循环，因为right后面一直不动

（2） 求中点的操作

这个和求左边界不一样，需要+1，即left+（right-left+1）/2（总个数为偶数个时取中点的时候取右边那个)，因为如果最后剩两个元素的时候，left一直找左边那个元素，那么将会进入死循环

（3）为啥nums[mid]==target左边界也要变

要寻找右边界，当nums[mid] == target，这个mid的位置不一定就是最右侧的那个边界，所以还要继续收缩左边界