死磕算法之二分查找法

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。博客源地址为zhixiang.org.cn https://blog.csdn.net/myFirstCN/article/details/80851013 ...
版权声明:本文为博主原创文章,未经博主允许不得转载。博客源地址为zhixiang.org.cn https://blog.csdn.net/myFirstCN/article/details/80851013


学习更多算法系列请参考文章:死磕算法之汇总篇


二分查找又称折半算法,此算法作为一个经典的查找算法是我们不得不掌握的算法

这个算法查找的前提是查找的数据是有序的,我们以数组为例,使用二分查找法进行查找的时候我们应该先定义三个字段:

1.left指向数组第一个数据

2.right指向数组最后一个元素

3.mid呢指向(left+right)/2位置的元素,就是他们中间的位置。


当我们要在一个数组中查找一条数据a时,有这么几个步骤:

  1. 首先我们拿a与mid比较,如果a与mid相等那么我们就成功找到了这个数据,程序停止。
  2. 如果a比mid小进行第3步,如果a比mid大进行第4步
  3. 既然a小于mid,那么mid与right之间的数肯定比a大,所以我们忽略它们,紧接着把right指向mid的前一个位置。(你可能会问为啥指向前一个位置不指向mid呀,因为我们已经确定了mid不等于a,那么我们就不需要在比较他了)
  4. 既然a大于mid,那么mid与left之间的数肯定比a小,所以我们忽略它们,紧接着把left指向mid的后一个位置。(不明白可以参考3哦)
  5. 如果left不大于right那么我们就还没有查找完毕,继续进行第一步。如果left已经大于了right,那么就代表在这个数组里我们没有找到想要的数据。

建议对二分查找不太熟悉的同学可以先在草稿纸上、电脑上或者脑海里定义一个0-16的有序数组跟着上边的步骤来查找一下数据5。

下面这个图是我画的图,来看一下跟你画的步骤或者想象的步骤一样么



如果上图你已经看明白了的话那么接下来我们就上代码吧,

public static void select(int[]num,int a){
    int left=0;
    int right=num.length-1;
    int m=(left+right)/2;
    while(left<=right){
        if(num[m]==a){
            System.out.println("在"+m+"位置找到");
            return;
        }
        if (num[m]>a){
            right=m-1;
        }else{
            left=m+1;
        }
        m=(left+right)/2;
    }
    System.out.println("没找到");
}

上面的方法使用了一个普通的循环的方式,二分还存在一种递归的写法,这里也分享出来

public static void select(int[]num,int a,int left,int right){
    if(left>right){
        System.out.println("没找到");
        return;
    }
    int m=(left+right)/2;
        if(num[m]==a){
            System.out.println("在"+m+"位置找到");
            return;
        }
        if (num[m]>a){
            right=m-1;
            select(num, a,left,right);
        }else{
            left=m+1;
            select(num, a,left,right);
        }
}

二分查找法讲到这里已经讲完了。在这里温馨提示大家,学习算法时,我们没必要拘泥于代码的实现,那没有意义。我的建议就是深入理解步骤,当你理解步骤以后代码是随你怎么玩都可以的。

学习更多算法系列请参考文章:死磕算法之汇总篇


二分查找又称折半算法,此算法作为一个经典的查找算法是我们不得不掌握的算法

这个算法查找的前提是查找的数据是有序的,我们以数组为例,使用二分查找法进行查找的时候我们应该先定义三个字段:

1.left指向数组第一个数据

2.right指向数组最后一个元素

3.mid呢指向(left+right)/2位置的元素,就是他们中间的位置。


当我们要在一个数组中查找一条数据a时,有这么几个步骤:

  1. 首先我们拿a与mid比较,如果a与mid相等那么我们就成功找到了这个数据,程序停止。
  2. 如果a比mid小进行第3步,如果a比mid大进行第4步
  3. 既然a小于mid,那么mid与right之间的数肯定比a大,所以我们忽略它们,紧接着把right指向mid的前一个位置。(你可能会问为啥指向前一个位置不指向mid呀,因为我们已经确定了mid不等于a,那么我们就不需要在比较他了)
  4. 既然a大于mid,那么mid与left之间的数肯定比a小,所以我们忽略它们,紧接着把left指向mid的后一个位置。(不明白可以参考3哦)
  5. 如果left不大于right那么我们就还没有查找完毕,继续进行第一步。如果left已经大于了right,那么就代表在这个数组里我们没有找到想要的数据。

建议对二分查找不太熟悉的同学可以先在草稿纸上、电脑上或者脑海里定义一个0-16的有序数组跟着上边的步骤来查找一下数据5。

下面这个图是我画的图,来看一下跟你画的步骤或者想象的步骤一样么



如果上图你已经看明白了的话那么接下来我们就上代码吧,

public static void select(int[]num,int a){
    int left=0;
    int right=num.length-1;
    int m=(left+right)/2;
    while(left<=right){
        if(num[m]==a){
            System.out.println("在"+m+"位置找到");
            return;
        }
        if (num[m]>a){
            right=m-1;
        }else{
            left=m+1;
        }
        m=(left+right)/2;
    }
    System.out.println("没找到");
}

上面的方法使用了一个普通的循环的方式,二分还存在一种递归的写法,这里也分享出来

public static void select(int[]num,int a,int left,int right){
    if(left>right){
        System.out.println("没找到");
        return;
    }
    int m=(left+right)/2;
        if(num[m]==a){
            System.out.println("在"+m+"位置找到");
            return;
        }
        if (num[m]>a){
            right=m-1;
            select(num, a,left,right);
        }else{
            left=m+1;
            select(num, a,left,right);
        }
}

二分查找法讲到这里已经讲完了。在这里温馨提示大家,学习算法时,我们没必要拘泥于代码的实现,那没有意义。我的建议就是深入理解步骤,当你理解步骤以后代码是随你怎么玩都可以的。

相关文章
|
28天前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
81 0
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
|
8月前
|
算法 Java 索引
算法系列之搜素算法-二分查找
二分查找是一种在`有序`数组中查找特定元素的算法。它的基本思想是通过将数组分成两半,逐步缩小查找范围,直到找到目标元素或确定目标元素不存在。
106 9
算法系列之搜素算法-二分查找
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
152 0
|
10月前
|
算法 索引
【算法】——二分查找合集
二分查找基础模版和进阶模版,查找元素位置,搜索插入位置,x的平方根,山脉数组的峰顶索引,寻找峰值,点名
|
12月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
114 1
|
12月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
137 0
|
12月前
|
消息中间件 存储 算法
一文搞懂二分查找算法!
一文搞懂二分查找算法!
374 0
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
143 0
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
算法
【算法】二分查找(整数二分和浮点数二分)
算法学习——二分查找(整数二分和浮点数二分)
166 0
【算法】二分查找(整数二分和浮点数二分)

热门文章

最新文章