文档章节

查找算法(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
杭州
程序员
私信 提问
二分查找(Binary Search)

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

野渡书生
2016/04/28
15
0
每天学习一点儿算法--二分查找

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

爱吃西瓜的番茄酱
01/07
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

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

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

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

泽毛
2017/12/12
0
0
递归 —— 二分查找法 —— 归并排序

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

CMusketeer
07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java.util.concurrent.atomic.AtomicLong 源码

类图: 源码: package java.util.concurrent.atomic;import java.util.function.LongUnaryOperator;import java.util.function.LongBinaryOperator;import sun.misc.Unsafe;......

狼王黄师傅
4分钟前
1
0
Java每天10道面试题,跟我走,offer有!(六)

51.HashMap的实现原理 HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。HashMap基于hashing原理,我们通过put()和get()方法储...

Java干货分享
10分钟前
1
0
剧调查黑客偏爱用 Python,可能是世界上最好的语言

导读 Python 变得越来越流行,在之前 9 月份的 TIOBE 排行榜中,Python 甚至挤下 C++,拿到第三名。而这有一部分原因应当归于黑客对 Python 的热衷。 据 Threatpost 报导,在 Imperva 最近一...

问题终结者
15分钟前
1
0
apollo生产环境配置-实践笔记(附搭建框架图)

前言 我们这个月上线了apollo1.1.1版本(生产环境),目前一切运行良好,故在此记个笔记。 首先,附上流程图: 简要介绍 一套apollo portal配置管理服务来同时管理pro、dev环境,但pro、dev...

开源小菜鸟2333
17分钟前
3
0
angular6 利用 ngContentOutlet 实现组件位置交换

这篇文章主要介绍了angular6 利用 ngContentOutlet 实现组件位置交换(重排),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧 ngContentOutlet指令介绍 ngCont...

嫣然丫丫丫
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部