开发者社区> 灰小猿> 正文

适用于各语言的二分查找算法,你get到了嘛?

简介: 适用于各语言的二分查找算法,你get到了嘛?
+关注继续查看

目录

二分查找算法定义

二分查找算法的过程剖析

二分查找算法的时间复杂度

二分查找的平均查找长度

二分查找的普通算法

二分查找的函数递归算法

Hello!大家好,我是努力赚钱买生发水的灰小猿,最近在做开发的时候偶然用到了之前数据结构上的二分查找算法,所以在这里和大家简单的分享一下适用于各种语言的二分查找算法编写。

那么什么叫二分查找算法呢?

二分查找算法定义

所谓二分查找算法,又叫折半查找,一般来说适用于数组元素,具体来说应该是已经按照顺序存储结构排列好的数组元素。它是一种效率较高的查找算法,通过对顺序表进行折半查找,从而获取到元素序列或查找次数的算法。

二分查找算法的过程剖析

我们假设现有的线性表中的元素是按照升序排列的,二分查找算法的思路就是将正在查找的表的中间元素和要查找的元素进行大小比较,若大小相等则输出该元素所在位置或查找次数;

若该中间元素不等于被查找元素时,会将该线性表以中间元素分成前后两部分的线性表,当中间元素小于被查找元素时,重新对后一部分的线性表进行二分查询;

反之,若中间元素大于被查找元素时,对前一部分的线性表进行相同的二分查找,当中间元素等于被查找元素时,查找结束;或直到线性表无法再进行分割时,查找结束,这个时候则说明表中无该元素。

下面是二分查找算法的查找图示:

二分查找算法的时间复杂度

二分查找的基本思想是:设有一个长度为n个元素的升序排列的数组a,分成前后大致相等的两部分,取中间元素a[n/2]与被查找元素(m)做比较,如果m=a[n/2],则找到m,算法中止;

如果m<a[n/2],则只要在数组a的左半部分继续二分查找m,如果m>a[n/2],则在数组a的右半部继续二分查找m.直到m=a[n/2]或数组不可再分割时查找结束。

因此时间复杂度就是while循环的次数,

总共有n个元素,

依次循环下去以后每次查找的元素个数就是:n、n/2、n/4、....n/2^k

若查找个数为n时,也就是第一次查找就找到了元素,则循环次数为1(也就是k=0的时候)所以循环次数为(k+1)

由于n/2^k取整后为(n/2^k)>=1

即令(n/2^k)=1

可得k=log2n,(是以2为底,n的对数)

所以时间复杂度可以表示O(h)=O(log2n)。

二分查找的平均查找长度

设待查找的元素为n,则折半查找的平均查找长度为:

二分查找的普通算法

以下为进行二分查找的函数方法,

传入的参数为升序排列的数组和要查找的元素,若查找到该元素,则返回查找次数,否则返回-1。

int binary_search(int[] a, int value)
{

    int low = 0;

    int high = a.length - 1;

    while (low <= high)

    {

        int middle = (low + high) / 2;

        if (a[middle] == value)

        {

            return middle;

        }

        if (value < a[middle])

        {

            high = middle - 1;

        }

        else

        {

            low = middle + 1;

        }

    }

    return -1;

}

二分查找的函数递归算法

传入的参数分别为:递增的数组、要查找的数值、起始查找位置(默认为0)、终止查找位置(默认为数组长度)

int binary_search_ecursion(int a[],int value,int low,int high) {

int middle=0;
if(low<=high)
{        
    middle = (low+high)/2;
    if (a[middle]==value) {
        return middle;
    }else {
        if (a[middle]<value) {
            return binary_search_ecursion(a, value, middle+1, high);
        }
        else {
            return binary_search_ecursion(a, value, low, middle-1);
        }
    }
}
return -1;

}

二分查找的思维方法适用于任何需要进行顺序表查找的语言,并且基本思路都是一样的。上面的二分查找函数是基于C#的,小伙伴们还可以进行延伸。

觉得有用记得点赞关注哟!

大灰狼期待与你一同进步!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
16377 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20660 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14895 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23574 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22329 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36416 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14732 0
+关注
灰小猿
一个用代码编织世界的工程师
70
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载