分治算法实现二分查找

 

      以前工作过程中学习的过程中写了很多测试程序，上周acer本本硬盘坏了，换了个新硬盘，数据全部丢失了，很多有用的东西就这样没了，可惜的很。以后把工作和学习中的到的东西还是放到网上来比较好点。

      最近，在论坛上看到有个人搞了个每日一题，觉得挺不错。最近在看数据结构，想想是否也可以来个每天看看数据结构。觉得那些东西虽然不是很难，但是若是坚持一段时间，量变必然会产生质变。而且每天花点时间在英语上，那么也会产生效果，背诵新概念的工程也该重启了，以前背了一段时间的，现在又忘了。

      javaeye月刊上有一个关于24点算法的讨论，很多人也参入讨论，有人说看谁20行以内解决，似乎不可能，不过参入讨论给的代码都比我的要长很多，看来自己还不是太笨。数据机构不会每天都写，但是每天都会看点，过段时间把排序的多个方法总结下，希望09年有所提高。昨天写的个利用归并和递归来实现的排序，有些问题，在4个数的时候是正确的，多于四个数字的时候，有一个数字不正确，还没找到原因。先把学习的一个递归二分查找贴出来。

     二分查找

int[] binary = {1,2,3,4,5,6,7,8,9};
		int lower = 0;
		int upper = binary.length-1;
		int curIn;
		
		int searchNum = 6;
		while(true)
		{
			curIn = (upper + lower)/2;
			if(binary[curIn] == searchNum)
			{
				System.out.println(searchNum + "存在于数组的" + curIn + "位置");
				return;
			}else if(upper < lower)
			{
				System.out.println(searchNum + "在数组中不存在");
				return;
			}else{
				if(binary[curIn]>searchNum)
				{
					upper = curIn - 1;
				}else if(binary[curIn]<searchNum)
				{
					lower = curIn + 1;
				}
			}
		}

 二分查找的递归实现，属于分治算法。分治算法， 常常是一个方法，这个方法中包含两个对自身的递归调用，但是只有一个真的执行了。

static int[] binary = {1,2,3,4,5,6,7,8,9};
	
	public static void main(String[] args) {
		
		int lower = 0;
		int upper =  binary.length;
		
		int searchNum = 6;
		
		binarySearch(searchNum,lower,upper);
	}

	private static void binarySearch(int searchNum, int lower, int upper) {
		int curItem = (lower + upper)/2;
		if(binary[curItem] == searchNum)
		{
			System.out.println(searchNum + "在数组的" + curItem + "位置上");
		}else if(lower>upper)
		{
			System.out.println("不存在该值");
		}
		else 
		{
			if(binary[curItem]>searchNum)
			{
				binarySearch(searchNum,lower,curItem-1);
			}
			if(binary[curItem]<searchNum)
			{
				binarySearch(searchNum,curItem+1,upper);
			}
		}
	}