登录/注册
千古壹号
804
占位
1
占位
0
浏览量
占位
粉丝
占位
关注
【算法】二分查找
千古壹号
2021-10-13 11:05:52 2021-10-13
18
0

二分查找

1.概念

如果想要在数组中查找一个数,最基本的方法就是暴力解法:一次遍历,这时候时间复杂度是O(N),二分查找就是其中的一种优化,时间复杂度是O(logN);具体做法是一步一步逼近直到找到。前提是数组需要是一个排序数组

定义:二分查找也称折半查找(Binary Search),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也可以是数组中某一区间的起始位置和终止位置

2.过程

  • 1.二分查找先初始化一个搜索空间,然后再这个搜索空间上去寻找某个值,注意这个搜索空间是有某种规律,比如说是有序的;
  • 2.因为这种规律,直接去看中间值,如果判断中间值和我们想要的结果的关系,比如搜索数字,看中间值和目标值的大小关系;
  • 3.如果mid>t,那证明应该去前半部分搜索;如果mid<t,那说明该去前半部分搜索;
  • 4.然后接着在新的搜索空间执行2,3;

关键 Knuth 大佬(发明 KMP 算法的那位)怎么说的: Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky... 思路很简单,细节是魔鬼

3.模板

//循环写法;
public int binarySearch(int[] nums, int target){
    int left = 0, right = num.length-1;
    while(left <= right){  //细节1:循环条件;
        int mid = left + ((right-left) >> 1);  
        //细节2:防止溢出,此外需要注意由于优先级的原因,需要添加括号;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1; //细节3:注意加减1;
        }else{
            right = mid - 1;
        }
    }
    return -1
}

//递归写法:
public int binarySearch(int[] nums, int target, int left, int right){
    if(left <= right){
        int mid = left + ((right-left)-1);
        if(nums[mid] == target){
            return mid;  //查找成功;
        }else if(nums[mid] > target){
            return binarySearch(nums, target, left, mid-1); //新的区间:左半区间;
        }else{
            return binarySearch(nums, target, min+1, right); //新的区间: 右半区间;
        }
    }
    return -1;
}

上述功能就是如果能在数组中找到目标值,就返回其索引,如果找不到,就返回其下标;如果目标值比中间值还大,那肯定在中间值右侧(因为数组已经排序好了),如果目标值比mid值小,那肯定在mid左侧。

  • 细节1:为什么while循环的条件时<=? 因为我们初始化的时候右侧区间是nums.length-1;所以是包括right的,即我们的区间是[left,right],这样一个左闭右闭的区间,把这个区间理解成搜索区间,即我们是在这样一个区间上搜索,那什么时候停止呢,两个原因:

  • 1.找到了目标值,那就停止;

  • 2.没找到目标值,但是搜索区间为空了,没得找了,这时候停止; 所以在最后一个=的时候,比如[2,2]这时候区间还不为空,万一就是这个2呢。

  • 细节2:为什么写成left+((right-left) >> 1); 这主要是为了防止溢出,记住就可以了,注意除以2,用位运算的话会比较快一点,而且记得带外面那个大括号;

  • 细节3: 为什么left = mid + 1,right = mid - 1? 想一下刚才搜索区间的概念,如果发现了索引mid不是要找的target,那自然要从将mid剔除掉,从mid的左边或者右边找起来了。

缺陷:上述算法存在一个缺陷就是不能返回左右侧边界,比如数组是[1,2,2,2,3], target是2,这时候返回的索引是2,没有办法返回左右边界。

4.样例

34. 在排序数组中查找元素的第一个和最后一个位置

33. 搜索旋转排序数组

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

仔细体会上面3个样例。

  • 1.解决了上面说到的不能返回左右边界的问题;
  • 2.这个问题是不完全有序数组的二分查找;基本思路就是将其往排序数组上赶,比较mid和left来确定是前半段有序还是后半段有序;
  • 3.是二分查找的一个问题,并不仅仅是查找某个值某个元素,重点去感受最后的left=right=mid;体会最后跳出循环的返回值;

5.体会

  • 当写成这样时:返回的left是第一个>=target的值的索引。

  • 如果原数组有target返回的就是第一个target的索引;

  • 如果没有那就是第一个比target大的值的索引(或者可以理解为要将target插入的位置索引);

之所以有上面的结论就在于最后一步一定是left=right=mid,而且mid左侧都<t,mid右侧都>=t,这时候执行判断,如果mid大于等于target,那就返回它了,也就是left,如果<target,那就执行left+1,返回的就是第一个>=target的值;

while(left <= right){
    int mid = left + ((right-left) >> 1);
    if(target <= nums[mid]){ //将等于合并过来;
        right = mid-1;
    }else{
        left = mid+1;
    }
}
    return left; //第一个比大于等于target的索引;
  • 注意查看上面中提到的二分法的模板和细节,注意什么时候带等号,什么时候不带等号;

  • 二分查找本质上就是一个不断缩小搜索空间的过程,比如我们找出某个值,就是在不断的把空间缩小;找出哪个数字乱序,也在不断的把空间缩小;求一个数的开根号,不断的缩小空间然后拿值去逼近。这个过程要多想一下,就是我们不断的缩小空间,然后每次都是拿这个空间上的中间值去做某种判断,然后去逼近我们的结果

  • 二分查找应用的前提就是一定是一个有序的,或者半有序的,如果是半有序的话原则是就是不断向有序上去赶,因为只有在有序的时候才能去二分;

  • 上面提供的二分查找的模板要始终明白在最后一步跳出循环前两点:

  • 1.最后一步一定是right=left=mid。

  • 2.mid左侧和右侧一定是已经有了规律的了。比如查找值的时候,mid左侧都比t值小,mid右侧都比t值大;比如判断从哪个数字开始乱了,mid左侧一定是整齐的,mid右侧一定是乱的。那这时候只要去判断一下mid的值就可以了。如果mid>t或者说mid乱了,那正好返回left也就是mid,如果mid<t或者说mid没乱,那left=mid+1,这不就正好是第一个大于t或者第一个乱的了吗。

原文: https://www.cnblogs.com/Curryxin/p/15103033.html

暂无评论