文档章节

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

haoran_10
 haoran_10
发布于 2016/07/15 16:38
字数 227
阅读 25
收藏 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
杭州
程序员
私信 提问
每天学习一点儿算法--二分查找

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

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

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

野渡书生
2016/04/28
15
0
算法知识梳理(8) - 二分查找算法及其变型

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

泽毛
2017/12/12
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

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

dqcfkyqdxym3f8rb0
2017/11/24
0
0
递归 —— 二分查找法 —— 归并排序

PS:什么是递归、二分查找、归并排序。 递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条...

CMusketeer
2018/07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

漏洞防御与修复工作

漏洞管理工作是企业安全建设必不可少的一环,在风险管理工作中,漏洞管理能够防患于未然,企业对漏洞管理有着广泛的基础建设和实践经验。但随着攻防技术的发展,传统漏洞管理的安全技术和管理...

linuxprobe16
41分钟前
1
0
MicroPython技术及应用前景

1 Micropython技术是什么? MicroPython极精简高效的实现了Python3语言。它包含Python标准库的一小部分,能在单片机和受限环境中运行。 1.1 MicroPython发展 由剑桥大学的理论物理学家乔治....

bodasisiter
47分钟前
2
0
跟我学Spring Cloud(Finchley版)-13-通用方式使用Hystrix

本节详细讲解使用Hystrix的通用方式。 简介 Hystrix是由Netflix开源的一个延迟和容错库,用于隔离访问远程系统、服务或者第三方库,防止级联失败,从而提升系统的可用性与容错性。Hystrix主要...

周立_ITMuch
56分钟前
1
0
🛠️Hanjst/汉吉斯特更新加JavaScript运行时优化等

这是 Hanjst/汉吉斯特 发布以来的首个主要升级更新版本。这次的主要升级更新的内容包括移除HTML Comments注释行, 优化在 Hanjst include模板文件时的JavaScript运行时环境。 Hanjst 在设计和...

wadelau
今天
2
0
OSChina 周六乱弹 —— 舔狗是没有好下场的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @我没有抓狂 :#今天听什么# #今天听这个# 分享 Nirvana 的歌曲《Smells Like Teen Spi...》 《Smells Like Teen Spi...》- Nirvana 手机党少...

小小编辑
今天
556
14

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部