文档章节

查找算法(1)--二分查找

haoran_10
 haoran_10
发布于 2016/07/15 16:38
字数 227
阅读 24
收藏 0
点赞 0
评论 0

简介:  二分查找算法是针对有序数组进行查找某个元素的算法,时间复杂度为Ο(logn) 。

 

一、主要步骤

有序数组arr(假设从小到大),待查找元素x

(1)、直接从中间一个元素开始找,mid = (0+arr.length)/2

(2)、如果arr[mid]大于x,说明目标索引在mid索引的左半边,把左边当作一个完整的数组继续查找

(3)、如果arr[mid]小于x,说明目标索引在mid索引的右半边, 把右边当作一个完整的数组继续查找

(4)、如果arr[mid]等于x,那就找到了

 

二、代码实现

public int search(int[] arr,int x) throws Exception{
	int start = 0;
	int end = arr.length-1;
	
	while(start<=end){
		int mid = (start+end)/2;
		
		if(arr[mid]>x){
			end = mid-1;
		}else if(arr[mid] == x){
			return mid;
		}else if(arr[mid]<x){
			start = mid+1;
		}
	}
	
	throw new Exception("not found"+x);
}

 

© 著作权归作者所有

共有 人打赏支持
haoran_10
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员
每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述,就是任何实现某种功能的代码片...

爱吃西瓜的番茄酱
01/07
0
0
二分查找(Binary Search)

1、定义 二分查找又称折半查找,它是一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 2、基本...

野渡书生
2016/04/28
15
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
算法知识梳理(8) - 二分查找算法及其变型

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/12
0
0
Java实现的二分查幸运飞艇平台出租找算法[递归]

二分查找又幸运飞艇平台出租 haozbbs.comQ1446595067 称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先...

oskksk
07/10
0
0
查找算法总结

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树 一、二分查找(常规) 题目描述: (牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/...

阿阿阿阿阿局
2016/07/28
20
0
从零基础学三分查找

转载请注明:http://www.cnblogs.com/ECJTUACM-873284962/ 今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章...

angel_kitty
2017/03/11
0
0
各种经典算法总结

二分排序 / 二分查找 算法思想:1、将数组排序(从小到大);2、每次跟中间的数mid比较,如果相等可以直接返回, 如果比mid大则继续查找大的一边,否则继续查找小的一边。 输入:排序好的数组 ...

长平狐
2013/01/06
85
0
跟黄哥学python序列文章之python二分查找算法

跟黄哥学python序列文章之python二分查找算法 在计算机科学中,二分查找算法(binary search)、也称折半搜索(英语:half-interval search), 二分搜索法、二分搜索、二分探索,是一种在有...

黄哥Python培训
2016/04/05
231
0
一份不错的php面试题(附答案)

一份不错的php面试题,附答案,有准备换工作的同学可以参考一下. 一、基础题 1. 写出如下程序的输出结果 <?php $str1 = null; $str2 = false; echo $str1==$str2 ? '相等' : '不相等'; $str3 ...

斑驳
2014/08/17
0
4

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Laravel5.5 MySQL配置、读写分离及操作

Laravel 让连接不同数据库以及对数据库进行增删改查操作: 参考:http://laravelacademy.org/post/854.html 配置读写分离 应用的数据库配置位于 config/database.php(但是数据库用户及密码等...

MichaelShu
5分钟前
0
0
TraitsUI与Mayavi实例

一:创建一个简单的TraitsUI与Mayavi实例 # -*- coding: utf-8 -*-from numpy import sqrt,sin,mgridfrom traits.api import HasTraits,Instancefrom traitsui.api import View,Item......

wangxuwei
10分钟前
0
0
Linux 查看用户

存储帐号的文件:/etc/passwd 存储密码的文件:/etc/shadow 查看当前系统所有用户 grep bash /etc/passwd root修改普通用户的密码 sudo passwd user_name 然后连续两次输入新的用户密码即可...

yeahlife
12分钟前
0
0
Webpack使用nodemon实时打包编译

业务场景: 1.编写一个npm组件包并且link到了项目文件中 2.需要不断的修改并run build编译npm包并且在项目run dev 查看效果 3.问题: 每次改完npm包都要手动run build编译十分的麻烦且低效,可不...

JamesView
23分钟前
0
0
电脑炸了,浪费我好几天时间,还是简要记下来吧

我的小本本一直在兢兢业业的干活,然而前几天说炸就炸了...... 爆炸现场: 软件: windows10 pro + EIS11+ 360卫士 BIOS:N1DET98W 2.24 硬件: Xeon E3 1505-V5 nv-M3000M thinkpadP70:20E...

Oh_really
27分钟前
0
0
Git之branch和checkout

1.branch是查看、创建、删除分支 #>git branch --helpNAME git-branch - List, create, or delete branchesSYNOPSIS git branch [--color[=<when>] | --no-color] [......

汉斯-冯-拉特
29分钟前
0
0
Mybatis拦截器之数据权限过滤与分页集成

需求场景 最近项目有个数据权限的业务需求,要求大致为每个单位只能查看本级单位及下属单位的数据,例如:一个集团军下属十二个旅,那么军级用户可以看到所有数据,而每个旅则只能看到本旅部...

佛系程序猿灬
38分钟前
9
0
SpringCloud 微服务 (十六) 服务追踪 Zipkin

问题 在服务中,有一个接口,该A接口中又调用了其他服务的B、C、D接口,出现一个请求耗时大的问题,这时候并不知道该B、C、D接口中哪个接口造成的耗时量,然后比如确定C服务接口出现的耗时量大,但...

___大侠
今天
0
0
Java面试基础篇——第八篇:抽象类与接口的区别

1.抽象类 抽象类:如果一个类中包含有抽象方法,或这个类使用abstract关键字修饰,则称这个类是抽象类。 抽象方法是什么呢?抽象方法就是指用abstract关键字修饰的方法。 需要注意的是:抽象...

developlee的潇洒人生
今天
2
0
jsoup 相关资料

1.jsoup 2.Jsoup概述 3.jsoup入门 4.jsoup Java HTML Parser 1.11.3 API

IT追寻者
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部