对于二分法的一些感想

前言

​ 本人最近一直在做一些算法方面的学习,最近也刷了一些力扣题目,我将我做过的题目分享到了我的GitHub上:算法题解可以供大家参考。最近在刷题的过程当中,我发现我老是在二分法的边界条件上出问题,经常是出现栈溢出的情况。所以想写一篇文章,记录一下我的学习心得与体会。

二分法用来干嘛

二分法往往是对一个有序的数据形式,进行查找特定值target的算法。

​ 该算法的优势是时间复杂度仅为O(log n),相较于顺序查找O(n)的时间复杂度有着明显的提升。

二分法的分类

​ 二分法有4个重要的值:target,start, end, mid.

​ 我将二分法的区间划分,分为3钟类型:

  1. 划分为[start,mid]和[mid+1,end]这两个区间

  2. 划分为[start,mid-1]和[mid,end]这两个区间

  3. 划分为[start,mid-1]和mid和[mid+1,end]这三个区间

    ​ 这三种分法的区别就是:mid该放在哪里

    ​ 该如何划分区间,是得视具体情况进行的。有的经典二分完全可以使用第三种分法(个人最喜欢的,因为边界条件最简单),但是有的时候,必须得用第一种和第二种形式,如:力扣第35题 。这题需要将mid归到左区间当中。(start<target <= mid)。

边界条件的难点

​ 情况3边界条件比较简单,当(start>end)的时候跳出循环即可,不会造成死循环或者栈溢出。但是情况2和情况3往往会造成边界条件分析不清晰导致产生死循环!

​ 为什么说边界条件难呢?如果mid值取得不对,容易造成死循环。且造成死循环往往是在剩下两个值的时候产生。这里举个例子:

在条件2的时候,下面的代码就会造成死循环!!!!

//在情况2的时候,该代码会造成死循环!!!
//假设array是从小到大排序的有序数组
static int BinarySearch(int[] array,int target,int start,int end){
    if(target < array[start] || target > array[end]) return -1;
    if(start == end){
        if(array[start] == target) return start;
        else return -1;
    }
    int mid = (start + end) / 2;
    if(array[mid] <= target)
        return BinarySearch(array,target,mid,end);
    else
        return BinarySearch(array,target,start,mid-1);
}

主函数为:

public static void main(String[] args) {
        int[] array = {0,2};
        int re = BinarySearch(array,0,0,1);
    	System.out.println(re);
    }

报错为:

Exception in thread "main" java.lang.StackOverflowError
	at demo.BinarySearch(demo.java:14)
	at demo.BinarySearch(demo.java:14)
	at demo.BinarySearch(demo.java:14)
	at demo.BinarySearch(demo.java:14)

但是我们将代码换成第一种情况,即:将第一个条件的 <= 变为 < 并将区间变化修改成第一种情况,将会是正确的!

//在情况1的时候,代码会成功运行!!!
//假设array是从小到大排序的有序数组
static int BinarySearch(int[] array,int target,int start,int end){
    if(target < array[start] || target > array[end]) return -1;
    if(start == end){
        if(array[start] == target) return start;
        else return -1;
    }
    int mid = (start + end) / 2;
    //将这里的<=该成<,并修改区间
    if(array[mid] < target)
        return BinarySearch(array,target,mid+1,end);
    else
        return BinarySearch(array,target,start,mid);
}

同样用第一个主函数跑,结果是正确的!

0

Process finished with exit code 0

我之前在这里老是理解很糊涂,走了不少弯路。但是,现在我再也不会在这里栽跟头了!!!!

解决边界条件

​ 大家也看见了,我数组会造成栈溢出,说明,这里的边界条件导致的栈溢出就是在数组剩下两个元素的时候发现。为什么会发生这样的情况其实可以这样区分:当只剩下两个元素的时候,用mid能不能使得这两个元素分开!

看第一个会造成死循环的例子:

​ 当数组是[left,left+1]这种情况的时候,mid的值为left,这时候,划分为[left,left-1]和[left,left+1]这两个区间,这样两个区间,没办法将left和left+1这两个元素分开,说明这样的mid是没有意义的。

​ 这时候我们需要将mid = mid+1即mid = left + 1可分开!因为这样,区间可以划分为[left,left]和[left+1,left+1]这样两个区间。这样才能将两个元素分开。

​ 而针对情况1,mid的值为left就可以分开,这时候,划分为[left,left]和[left+1,left+1]这样两个区间。

​ 以后碰到这种情况,牢记分开元素准则,我们只需要当场复盘一下这个过程即可避免栈溢出的产生!

相关推荐

发表评论

路人甲

网友评论(0)