文档章节

二分查找

人觉非常君
 人觉非常君
发布于 06/24 00:33
字数 493
阅读 17
收藏 0
点赞 0
评论 0

        二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空,则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半,其时间复杂度是O(logN)。

package com.query.half.utils;

import java.util.Comparator;

/**
 * 二分查找  工具类
 * @author huang
 *
 */
public class HalfQueryUtil {

	private HalfQueryUtil() {
		super();
	}

	public static <T> int binarySearch(T[] list, T key, Comparator<T> comparator) {
		if(null == list || null == comparator) {
			return -1;
		}
		int retIndex = -1;
		int start = 0;
		int end = list.length;
		int middle = 0;
		int compareResult = 0;
		while(start < (end-1)) {
			middle = (start + end) >>> 1;
			compareResult = comparator.compare(list[middle], key);
			if(compareResult > 0) {
//				start = start;
				end = middle;
			} else if(compareResult < 0) {
				start = middle;
//				end = end;
			} else {
				retIndex = middle;
				break;
			}
		}
		return retIndex;
	}
	
	public static <T extends Comparable<T>> int binarySearch(T[] list, T key, int start, int end) {
		if(start <= end) {
			int middle = (start + end) >>> 1;
			int compareResult = key.compareTo(list[middle]);
			if(compareResult > 0) {
				start = middle + 1;
//				end = end;
				return binarySearch(list, key, start, end-1);
			} else if(compareResult < 0) {
//				start = start;
				end = middle - 1;
				return binarySearch(list, key, start, end-1);
			} else {
				return middle;
			}
		}
		return -1;
	}	
}

注:需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式,因为加法运算可能导致整数越界,这里应该使用以下三种方式之一:

end + (start – end) / 2

end + (start – end) >> 1

(end + start) >>> 1

 

© 著作权归作者所有

共有 人打赏支持
人觉非常君
粉丝 4
博文 23
码字总数 13433
作品 0
浦东
二分查找(Binary Search)

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

野渡书生
2016/04/28
15
0
二分查找判定树

5、二分查找判定树  二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判...

天天顺利
2015/09/12
3.5K
0
每天学习一点儿算法--二分查找

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

爱吃西瓜的番茄酱
01/07
0
0
二分搜寻法 ( 搜寻原则的代表)

二分搜寻法 ( 搜寻原则的代表) 1.二分查找又称折半查找,它是一种效率较高的查找方法。 2.二分查找要求:(1)必须采用顺序存储结构 (2).必须按关键字大小有序排列 3.原理:将数组分为三...

郑加威
2017/04/18
0
0
JavaScript数据结构与算法(二分查找算法)

介绍 二分查找必须在有序的数中使用.二分查找算法应用范围非常广泛,首先来简单来下二分查找。 找到其中一个与Key相等元素 找到第一个与key相等的元素 找到第一个大于等于key的元素 找到最后...

fiveoneLei
昨天
0
0
从零基础学三分查找

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

angel_kitty
2017/03/11
0
0
二分查找 : 那个隐藏了 10 年的 Java Bug

原文出处:ccmouse 一个偶然的机会,我想起以前还在谷歌上班的时候,有时候大家会在饭桌上讨论最新想出来的一些面试题。在众多有趣又有难度的题目中,有一道老题却是大家都纷纷选择避开的,那...

ccmouse
2017/09/02
0
0
简单描述一下二分查找和顺序查找

<?php class search { // 查找的源数组 private $array = array(1,2,3,5,7,6,4,8); /** * 顺序查找法 * @param $val 要查找的值 */ public function query_search($val) { foreach ($this->......

saintatgod
2014/03/26
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

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

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

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

泽毛
2017/12/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring配置xml启动报错 Connot find 'beans'

1.我们先看一下spring的原始配置 <?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSc......

江湖鱼大虾
4分钟前
0
0
与女儿谈商业模式 (4):戴尔的成功秘诀

分类:与女儿谈商业模式 | 标签: 戴尔 经济学 陈志武 2007-05-15 10:26阅读(7434)评论(36)   2007年5月《创富志》与“女儿谈商业模式”专栏 (之四)   戴尔的成功秘诀   陈志武   ...

祖冲之
13分钟前
0
0
www.w3.org被qiang导致logback报错:Connect reset

web项目部署到tomcat后,web项目中的logback不能运行,报错信息如下: Reported exception: ch.qos.logback.core.joran.spi.JoranException: I/O error occurred while parsing xml file......

浮躁的码农
27分钟前
0
0
JDeveloper中文乱码解决

全局设置字体; 全局设置环境编码; 项目设置编译器环境编码。

wffger
55分钟前
2
0
MySQL主从介绍 , 准备工作,配置主,配置从, 测试主从同步

MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主从后,在A上写数据,另外一台B也会跟着写数据,两者数据实时同步的 MySQL主从是基于binlog的,主上须开启bin...

TaoXu
今天
2
0
线性代数学习总结

亭子happy
今天
1
0
Java8:Lambda表达式增强版Comparator和排序

1、概述 在这篇教程里,我们将要去了解下即将到来的JDK 8(译注,现在JDK 8已经发布了)中的Lambda表达式——特别是怎样使用它来编写Comparator和对集合(Collection)进行排序。 这篇文章是...

孟飞阳
今天
0
0
从架构到组件,深挖istio如何连接、管理和保护微服务2.0?

近几年我一直从事于微服务系统的设计以及实现方面的工作,属于微服务架构一线实践者。之前做过一些单体系统的微服务改造,在微服务拆分、治理等方面都有一定的经验。 本人比较特殊一点的经历...

xiaomin0322
今天
1
0
基于vue的h5文件切片上传(获取文件md5,实现秒传、进度条实现)

template <button @click="file"></button><label ref="upload" style="position: relative;"> <input type="file" @change="selectFile" style="position: abs......

hkaikai
今天
2
0
Spring Boot 2.0 项目实现自同步AD域账号

在通过Spring Boot的自动化装配功能及JDK自带的LDAP模块,可通过如下几个简单步骤实现业务系统自动同步AD域账号功能。 1. Java自带ldap搜索域账号信息核心代码: try { LdapContext ctx...

B超
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部