文档章节

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

haoran_10
 haoran_10
发布于 2016/07/15 16:38
字数 227
阅读 24
收藏 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
算法知识梳理(8) - 二分查找算法及其变型

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

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

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

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

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

CMusketeer
07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
4
0
一个手机装天下,走遍中国都不怕!

导读 “1200元(人民币,下同),微信支付,可以,你扫我。”来自西非马里共和国的展商Albert拿着手机,和一位买走他手鼓的中国游客用简单的汉语交流着。 近日,“第十四届中俄蒙经贸洽谈暨商品...

问题终结者
昨天
3
0
Redis的“死键”问题

大规模的数据库存储系统中,数据的生命周期管理是很有必要的;从业务角度发现过期数据,数据归档和数据碎片整理等。以MySQL为例,1个运行很久的TB级MySQL实例中,极有可能数百GB的数据,对业...

IT--小哥
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部