文档章节

二分查找

人觉非常君
 人觉非常君
发布于 06/24 00:33
字数 493
阅读 24
收藏 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

 

© 著作权归作者所有

共有 人打赏支持
上一篇: Centos7.4安装Redis
下一篇: 冒泡排序
人觉非常君
粉丝 6
博文 43
码字总数 29951
作品 0
浦东
私信 提问
二分查找(Binary Search)

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

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

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

天天顺利
2015/09/12
3.5K
0
算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重要的基础问题 查找问题的基础:二分查找法 Binary Search 对于有序...

天涯明月笙
2017/09/16
0
0
二分搜寻法 ( 搜寻原则的代表)

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

郑加威
2017/04/18
0
0
每天学习一点儿算法--二分查找

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

爱吃西瓜的番茄酱
01/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

TiQuery:All Diagnosis in SQL | TiDB Hackathon 优秀项目分享

本文作者是来自 TiNiuB 队的黄梦龙同学,他们的项目 TiQuery 在本届 TiDB Hackathon 2018 中获得了三等奖。 TiQuery 可以搜集诊断集群问题所需要的信息,包括集群拓扑,Region 分布,配置,各...

TiDB
9分钟前
2
0
git 分支创建合并流程图

gentlelions
17分钟前
2
0
Kali Linux常用服务配置教程DHCP服务原理

Kali Linux常用服务配置教程DHCP服务原理 动态主机配置协议(Dynamic Host Configuration Protocol,简称DHCP)是一个局域网的网络协议,基于UDP协议工作。它主要有两个用途:第一,给内部网...

大学霸
18分钟前
1
0
控制台打印图片

function dev(){ if (window.console){ console.log("%c\n ", "font-size:100px;background:url('http://gmcyzs.com/resources/images/logo.png') no-repeat"); console.log('%c 深务平台,\......

羊皮卷
25分钟前
0
0
MyBaties的二级缓存

二级缓存介绍 在上文中提到的一级缓存中,其最大的共享范围就是一个SqlSession内部,那么如何让多个SqlSession之间也可以共享缓存呢,答案是二级缓存。 当开启二级缓存后,会使用CachingExec...

嘴角轻扬30
25分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部