文档章节

二分查找

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

 

© 著作权归作者所有

共有 人打赏支持
人觉非常君
粉丝 5
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部