庞果网的二分查找挑战

上周末在ITEYE上看到一个标题‘在充足时间下，只有百分之二十程序员能成功完成的二分查找’，当时心想，对于算法虽然基础不是很精通，但是基础的还没问题，抱着好奇心点了进去，原来是一个编程挑战，题目当然是实现二分查找，还有一个附属条件是当有多个值相同时，返回最小下标，看看时间，一个小时呢，心想应该很快能够实现的，当然首先想到是写一个递归算法，写递归算法首先的是要确定出口，当时很自然的觉得应该是开始下标应该小于等于结束下标，于是就开始实现了，结果到后来发现查找数组里有的数据时没有问题，查找没有的值时会出现栈溢出，发觉自己还是心理素质不够好，当时就不淡定了，想着自己的想法应该没有问题，后来时间快到了，就勉强提交了只能查找存在数值的版本上去。最近这周任务比较紧，也就没来得及细细思索这个问题，不过一直挂在脑子里，今天下午终于有点时间，于是挤出来重新实现了一遍，发现问题就在递归出口上，其实当时也应该想到栈溢出的一种可能就是递归无出口的问题，于是最终去掉了首尾下标相等的条件，也就实现了查找了，当然重复值返回最小下标应该是比较简单了，在找到查找的值时再向前来一次二分查找就可以了。

package com.johnson.algo;

public class BinarySearch {
	public static int search(int[] arr, int start, int end, int val) {
		if (start < end) {
			int mid = start + ((end - start) >> 1);
			if (val == arr[mid]) {
				int k = -1;
                                //这里再进行一次二分查找即可实现返回重复值的最小下标
				if ((k = search(arr, start, mid, val)) != -1) {
					return k;
				}
				return mid;
			} else if (val < arr[mid]) {
				return search(arr, start, mid, val);
			} else {
				return search(arr, mid + 1, end, val);
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] arr = { 0, 3, 4, 6, 11, 11, 11, 87 };
		System.out.println(search(arr, 0, arr.length - 1, 11));
	}
}