二分查找算法（递归-非递归）

二分查找( binary search)

先来个比较官方的解释：

二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 - from *

以上介绍参考自*（PS：非常建议大家多上Google，多上Wikipedia，相信我，你会爱上它们的，哈哈~）

好，看完比较正式的解释如果不太理解，没关系，拿图来说话：

二分法首先考察中间元素a[mid]，如果该值是我们要找的值，那好极了，直接找到了；如果不是的话，由于我们已经知道数组是排好序的（二分法要求待查找的数组是有序的，本例假设是升序的，降序其实是一样的），那就看目标值target和a[mid]的关系是怎样的：如果a[mid] > target则说明目标值target如果存在的话一定在a[mid]的左侧，因为左侧都比a[mid]小；如果a[mid] < target则说明目标值如果存在的话一定在a[mid]的右侧，因为右侧都比a[mid]大。

因为a[mid]处在数组的中间位置，所以它的左侧或者右侧都是数组的一半，这样每一次我们通过a[mid]和target的比较就可以排除掉一半的数据。最后只有两种情况，要么我们找到了目标值，要么我们排除了所有数据没有找到目标值。

由此看来，在处理已排序数据的查找工作时，二分查找法显然效率高于线性查找法。这种优势在数据量越大的时候越明显。

比如说，现在有序数组中含有100万个数据，我们要求查找特定元素。如果使用线性查找法，我们必须对这一100万个数据依次考察以确定出目标元素是不是存在，最好的情况是目标元素在数组的第一个位置a[0]，这样只要一次就查找到目标元素了，最坏情况是目标元素在数组的最后a[999999]，这样我们就得比较100万次才能知道目标元素到底在不在，平均下来看的话也需要50万次比较。而如果使用二分查找法，我们大约做20次比较就可以知道目标元素是不是存在于数组中了。

50万 VS 20！

是不是很惊悚？为了达到目的我们可以使用不同的算法，但是这些算法之间的差异真的很大！在数据量越大的时候二分法的优势越明显。

/**
 * 
 */
package test2;

/**
 * @author lee
 *
 */
public class BinarySearch {

	/**
	 * @author lee 2017年3月12日 下午6:53:49
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {1, 5, 6, 12, 15, 19, 23, 26, 30, 33, 37, 42, 53, 60};
		int target = 12;
		int index = binarySearch1(a, 0, a.length-1, target);
		if(index > -1)
		{
			System.out.println("找到index值："+index);
		}
		else {
			System.out.println("not found");
		}
	}
	/**
	 * 递归实现二分查找
	 * @param a		  已排序数组（假设是从小到大）
	 * @param l		  数组左边界	
	 * @param r		  数组右边界
	 * @param target 要查找的值
	 * @return       要查找的值在数组中的位置，如果没找到则返回-1
	 * @author lee 2017年3月12日 下午7:05:43
	 */
	static int binarySearch1(int[] a,int l,int r,int target)
	{
		if(l<=r)
		{
			//中间位置，为了防止溢出使用这种方式求中间位置，没有使用mid = (l+r)/2;
			int mid = l + (r - l)/2;
			//中间的值比目标值小，则在右半边继续查找
			if(a[mid] < target)
			{
				return binarySearch1(a, mid+1, r, target);
			}
			//中间的值比目标值大，则在左半边继续查找
			else if(a[mid] > target)
			{
				return binarySearch1(a, l, mid-1, target);
			}
			//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
			else {
				return mid;
			}
		}
		return -1;
	}
	/**
	 * 非递归实现二分查找
	 * @param a		  已排序数组（假设是从小到大）
	 * @param l		  数组左边界	
	 * @param r		  数组右边界
	 * @param target 要查找的值
	 * @return       要查找的值在数组中的位置，如果没找到则返回-1
	 * @author lee 2017年3月12日 下午7:05:43
	 */
	static int binarySearch2(int[] a,int l,int r,int target)
	{
		while(l<=r)
		{
			//中间位置，为了防止溢出使用这种方式求中间位置，没有使用mid = (l+r)/2;
			int mid = l + (r - l)/2;
			//中间的值比目标值小，则在右半边继续查找
			if(a[mid] < target)
			{
				l = mid + 1;
			}
			//中间的值比目标值大，则在左半边继续查找
			else if(a[mid] > target)
			{
				r = mid - 1;
			}
			//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
			else {
				return mid;
			}
		}
		return -1;
	}
}