当前位置: 首页 > 技术随笔 > 二分查找入门详解

二分查找入门详解

在平常的软件开发过程中,我们经常都会遇到需要在数组或集合中查找某个指定元素的情况。通常情况下,我们会使用按照自然顺序的方式来查找数组中的是否存在指定的元素。例如:

/**
 * 从数组中顺序查找是否存在指定的元素,如果存在则返回该元素的索引,否则返回-1
 * 
 * @param array 指定所查找的数组
 * @param search 待查找的元素
 * @return
 */
public static final int search(int[] array, int search) {
	for (int i = 0; i < array.length; i++) {
		if (array[i] == search) {
			return i;
		}
	}
	return -1;
}

不过,作为程序员更应该掌握能够提高查找效率的相关算法,比如——二分查找(binary search)二分查找是编程技术领域一种非常著名也比较简单的算法,它可以使得查找元素的效率得到几何量级的提高。不过,值得注意的是,二分查找的使用前提是:所查找的排列必须是一个有序(从大到小或从小到大)的排列

二分查找算法,简单点说,就是先将一个有序排列最中间的元素x取出来与查找的元素进行比较,从而确定查找的元素是在x的左侧还是右侧(或者是x本身),从而缩小查找的区间范围。然后再继续取出缩小范围后的有序排列中最中间的元素与查找的元素进行比较,再次确定查找的元素是在其左侧还是右侧,通过多次这样的循环筛选,不断缩小查找的区间范围,最后确定待查找元素的位置。

如上所述,二分查找算法是一种比较简单的算法。不过,遗憾的是,美国著名的编程技术专家乔恩·本特利(Jon Bentley)在1986年的经典名著《编程珠玑》(Programming Pearls)中提到他的一个调查结果:居然有90%左右的程序员无法在2小时内使用自己喜欢的编程语言正确编写出二分查找的代码。因此,我们不得不在这里老生常谈似的,再次回顾一下二分查找算法代码的实现:

/**
 * 使用二分查找算法在有序数组中查找指定的元素,如果找到则返回对应的数组索引,否则返回-1
 * @param array 待查找的有序数组(注意,是有序数组!)
 * @param search 需要查找的元素
 * @return
 */
public static final int binarySearch(int[] array, int search) {
	int start = 0, end = array.length - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (array[mid] < search) {
			start = mid + 1;
		} else if (array[mid] > search) {
			end = mid - 1;
		} else {
			return mid;
		}
	}
	return -1;
}

// 程序主方法
public static void main(String[] args) {
	int[] array = { 0, 12, 25, 38, 49, 65, 81 }; //必须是事先已经排序好的数组
	System.out.println(binarySearch(array, 65)); // 输出:5
}

上述代码也是网络上其他介绍二分查找算法的文章中给出的完整代码实现,可是这样就结束了吗?No,当然不是,这还不是完整的二分查找实现代码。众所周知,二分查找是针对一个有序排列而设计的数组查找算法,既然是有序排列,不仅从小到大的排列是有序排列,从大到小的排列也是有序排列。但是,上述代码却只能实现对从小到大的有序排列的二分查找,如果是从大到小的有序排列,它就无能为力了。因此,我们需要针对从大到小的有序排列的情况来完善上述代码:

/**
 * 使用二分查找算法在有序数组中查找指定的元素,如果找到则返回对应的数组索引,否则返回-1
 * 
 * @param array 待查找的有序数组(注意,是有序数组!)
 * @param search 需要查找的元素
 * @return
 */
public static final int binarySearch(int[] array, int search) {
	int start = 0, end = array.length - 1;
	// 判断当前数组为正向排序(从小到大)还是逆向排序(从大到小)
	boolean isPositive = array[end] >= array[start];
	while (start <= end) {
		int mid = (start + end) / 2;
		if (array[mid] < search) {
			if (isPositive) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		} else if (array[mid] > search) {
			if (isPositive) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		} else {
			return mid;
		}
	}
	return -1;
}

// 程序主方法
public static void main(String[] args) {
	int[] array = { 81, 65, 49, 38, 25, 12, 0 };
	System.out.println(binarySearch(array, 65)); // 输出:1
}

备注:真正完整的二分查找算法实现应该兼容多种数据类型,为了便于读者阅读理解,上述代码仅实现了针对int类型的有序数组的二分查找。

9 0
我们认为: 用户的主要目的,是为了获取有用的信息,而不是来点击广告的。因此本站将竭力做好内容,并将广告和内容进行分离,确保所有广告不会影响到用户的正常阅读体验。用户仅凭个人意愿和兴趣爱好点击广告。
我们坚信:只有给用户带来价值,用户才会给我们以回报。
CodePlayer技术交流群1CodePlayer技术交流群1

帮朋友打一个硬广告:

P2P网贷系统(Java版本) 新年低价大促销,多年P2P技术积累,系统功能完善(可按需定制,可支持第三方存管、银行存管),架构稳定灵活、性能优异、二次开发快速简单。 另可提供二次开发、安装部署、售后维护、安全培训等一条龙服务。

外行看热闹,内行看门道。可以自信地认为,在系统设计上,比市面上的晓风、迪蒙、方维、绿麻雀、国融信、金和盛等P2P系统要好。
深圳地区支持自带技术人员现场考察源代码、了解主要技术架构,货比三家,再决定是否购买。

也可推荐他人购买,一旦完全成交,推荐人可获得实际售价 10% 的返现。
有意向者,详情请 点击这里 联系,工作时间立即回复。

数据排序