[转载 + 实现] 只有10%程序员能正确实现二分查找算法

在CSDN看到一篇题为《只有10%程序员能正确实现二分查找算法》的文章(原文链接http://news.csdn.net/a/20100423/218099.html)，很有意思，在不进行测试的情况下，你能保证所写的二分查找是完全正确的吗？

 

只有10%的程序员可以写出二分查找

每次翻开《编程珠玑》，我都会先看一看下面这几段文字： 

二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。 

多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。 

我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。 

我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。 

——乔恩·本特利，《编程珠玑（第1版）》第35-36页

 

自己也尝试了一下，没有用传说中好几个小时那么长的时间，也因慎重不是几分钟解决，在检查了一会儿，认为正确的情况下，代码如下：

 

private static int binarySearch(int[] sortedData, int targetValue) {
		return subBinarySearch(sortedData, 0, sortedData.length - 1,
				targetValue);
	}

	private static int subBinarySearch(int[] sortedData, int startIndex,
			int endIndex, int targetValue) {
		// 1 element
		if (startIndex == endIndex) {
			int onlyValue = sortedData[0];
			if (onlyValue == targetValue)
				return onlyValue;
			else
				return -1; // -1 indicates that target value is not found.
		}

		// 2 elements
		if (endIndex - startIndex == 1) {
			if (sortedData[startIndex] == targetValue)
				return startIndex;
			if (sortedData[endIndex] == targetValue)
				return endIndex;
			else
				return -1;
		}

		// 3 elements or more
		int middleIndex = (startIndex + endIndex) / 2;
		int middleValue = sortedData[middleIndex];
		if (middleValue == targetValue)
			return middleIndex;
		else if (middleValue > targetValue) {
			return subBinarySearch(sortedData, startIndex, middleIndex - 1,
					targetValue);
		} else { // if (middleValue < targetValue)
			return subBinarySearch(sortedData, middleIndex + 1, endIndex,
					targetValue);
		}
	}

 

自己进行了一些简单的测试，尚未发现错误，如果大家看到哪里有缺陷请指出来，非常感谢！欢迎交流！

评论

1 楼 paradise2009 2013-10-25  

你的code有bug

int middleIndex = (startIndex + endIndex) / 2;  

这句有可能会超出int 65535的范围.

推荐写法:

int mid = lo + (hi - lo) / 2;

或者一个快速的通过位移实现的方法是:

int mid = (lo + hi) >>> 1; 

参考: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582

谢谢!