查找算法之折半查找_采用折半查找算法有序表7.15.18.21.27.36.42.48.51.54.60.72中寻找值为-程序员宅基地

技术标签: java  数据结构  

折半查找又称为二分查找,其要求查找的序列是一个有序序列(递增或递减),其查找过程:折半查找就是每查找一次,就将序列减少一半,不断缩小查找范围,直到查找成功(也可能查找失败)。
例如:
一个有序序列array为(2,4,5,7,9,15,18,20,23,25,28),要查找的元素key为7;
我们定义三个指针left、mid、right分别指向序列的下界、序列的中间位置、序列的上界,即left=0,right=array.length-1=10,mid=(left+right)/2=5;array[left]=2,array[right]=28,array[mid]=15。
1)首先我们将array[mid]与key进行比较,mid>key,那我们下一次只需要在序列的左半边进行查找,left=0,right=mid-1=4,mid=(left+right)/2=2;array[left]=2,array[right]=9,array[mid]=5。
2)继续将array[mid]与key进行比较,key>array[mid],left=mid+1=3,right=4,mid=(left+right)/2=3;array[left]=7,array[right]=9,array[mid]=7。
3)再将array[mid]与key进行比较,array[mid]=key,查找成功。

算法实现:

public class binary_Search {
    public int search(int[] array,int searchKey){
        int left = 0, mid , right = array.length - 1;
        while(left <= right){
            mid = (left + right)/2;
            if(mid == searchKey){
                return mid;   //返回下标
            }
            if(mid < searchKey){
                right = mid - 1;
            }
            if(mid > searchKey){
                left = mid + 1;
            }
        }
        return -1;  //查找失败
    }

    public static void main(String[] args){
        search_Seq ss = new search_Seq();
        int[] array = {2,4,5,7,9,15,18,20,23,25,28};
        int searchKey = 7;
        int ans = ss.search_Seq(array,searchKey);
        System.out.println(searchKey+"是数组的第"+(ans+1)+"位元素");
    }
}

运行结果:
折半查找.png

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44044431/article/details/107288540

智能推荐

android新浪微博登录获取用户信息_微博软件上是也有获取用户lp-程序员宅基地

文章浏览阅读2.6k次。第一步:准备工作 在新浪微博开发者平台http://open.weibo.com/apps/注册并上传应用各种信息(比较多)获取到appkey,关于签名信息最好使用新浪提供的工具省心些,默认的授权回调页https://api.weibo.com/oauth2/default.html要与代码中一致。第二步:下载新浪SDK添加到工程librepositories { flatDi_微博软件上是也有获取用户lp

python的pandas数据处理_pandas minor_xs用法-程序员宅基地

文章浏览阅读424次。1、numpy纯属组,有一维二维三维数组,但是无索引与列名,所以计算速度快2、series一维数组,有标签,(主要是用在时间序列的数据上)3、dataframe二维数据 表格里横向A B ,纵向A B4、panel三维数据 由items major_xs minor_xs 组成,可有multiindex多索引的数据格式(iteritem是每一列的加总,iterrow..._pandas minor_xs用法

超详细---使用QRCode生成二维码并生成到PDF上_java 二维码 添加到doc模板-程序员宅基地

文章浏览阅读5.1k次。突发奇想想生成一个这样的一个带二维码的pdf:然后就开始做了废话不多说了直接上代码:POM.XML(所需要的jar)里面的jar可能不全,根据错误提示需要自己再去引入jar<!-- PDF相关 start --> <dependency> <groupId>org.apache.poi</groupId> ..._java 二维码 添加到doc模板

IDEA 报错 需要class, interface或enum_idea需要class interface或enum-程序员宅基地

文章浏览阅读1.3w次,点赞11次,收藏11次。需要class, interface或enum或者显示非法字符将右下角的UTF-8转换为GBK再将GBK转为UTF-8就OK啦!_idea需要class interface或enum

Numpy基础学习_np.diff python-程序员宅基地

文章浏览阅读476次。文章目录资源一些概念2.1numpy属性2.2numpy的创建array2.3numpy的基础运算资源Numpy & Pandas (莫烦 Python 数据处理教程)一些概念在统计学语言的角度来看,一维数组可以称为vector(向量);而二维数组可以称为matrix(矩阵);三维以上的就没有特殊名称,全都称为array。向量、矩阵都可以看作是数组的特殊形式,被数组这个概率所包含。2.1numpy属性import numpy as nparray = np.array([[1, 2,_np.diff python

HDFS集群扩容节点-程序员宅基地

文章浏览阅读499次。在企业中,经常需要根据业务的发展对HDFS集群进行节点扩容。比如我们要添加一个新DataNode节点到集群中:新节点主机名:bigdata114I..._hdfs扩节点

随便推点

Android 生成自己的 implementation 依赖_安卓 implementation 写法-程序员宅基地

文章浏览阅读1k次。在开发过程中,有些工具总是重复使用, 可以自己创建个工具包 , 这样就可以在新的项目中直接引用而不需要每次都进行复制粘贴,节省了很多不必要的时间.接下来一步一步实现:第一步需要在工程目录下的 build.gradle 中添加 dependencies 部分classpath 'com.github.dcendents:android-maven-gradle-plugin:2.1'第二步在library的build.gradle文件增加apply plugin: 'com.gith_安卓 implementation 写法

java反编译工具jd-gui使用_jd反编译怎么使用-程序员宅基地

文章浏览阅读6.4k次。《JD-GUI》是一款反编译软件,JD分为JD-GUI、JD-Eclipse两种运行方式,JD-GUI是以单独的程序的方式运行,JD-Eclipse则是以一个Eclipse插件的方式运行。基础知识什么是反编译器大家都知道,将源代码转换成二进制执行代码的过程叫“编译”,比如将C源代码编译成exe可执行文件;那么把二进制执行代码的过程就叫“反编译”,比如把exe转换为C源代码就叫“反编译”..._jd反编译怎么使用

java-字符串String_"用java定义一个字符串为string s1=\"hao are you today?\"完成下列-程序员宅基地

文章浏览阅读224次。在 Java 中,字符串被作为 String 类型的对象处理。 String 类位于 java.lang 包中。默认情况下,该包被自动导入所有的程序。一、创建String对象的方法1、创建一个字符串对象Hello,名为s1 String s1 = “Hello”;2、创建一个空字符串对象,名为s2 String s2 = new String();3、创_"用java定义一个字符串为string s1=\"hao are you today?\"完成下列操作(1)获取"

CUDA——"从入门到放弃"_cuda从入门到放弃-程序员宅基地

文章浏览阅读522次,点赞3次,收藏7次。CUDA——"从入门到放弃"开篇一张图,后面听我编1. 知识准备1.1 中央处理器(CPU)中央处理器(CPU,Central Processing Unit)是一块超大规模的集成电路,是一台计算机的运算核心(Core)和控制核心( Control Unit)。它的功能主要是解释计算机指令以及处理计算机软件中的数据。中央处理器主要包括运算器(算术逻辑运算单元,ALU,..._cuda从入门到放弃

线性代数-MIT 18.06-5(a)_mit线性代数习题-程序员宅基地

文章浏览阅读651次。本文在学习《麻省理工公开课 线性代数 MIT 18.06 Linear Algebra》总结反思形成。每5讲作为一个专题,本次5讲的题目为第21讲:特征值和特征向量;第22讲:对角化和矩阵的幂;第23讲:微分方程和指数矩阵;第24讲:马尔科夫矩阵、傅里叶级数;第23讲:复习二_mit线性代数习题

Linux下如何定时执行php脚本?Linux下如何设置定时任务?Crontab定时执行程序_linux设置定时任务运行php脚本-程序员宅基地

文章浏览阅读396次。本文转载自:http://blog.sina.com.cn/s/blog_8edc37a80101cgub.html(2013-06-06 10:37:46)转载▼标签:linux下定时执行phpcrontab定时任务linuxcrontab-e编辑crontabphp的shell脚本 Linux下如何定时执行php脚本?_linux设置定时任务运行php脚本

推荐文章

热门文章

相关标签