算法初步之二分法查找

从来没有认真学过数据结构，也没写过什么像样的算法，注定我的程序员之路走的很艰辛，是该改变的时候，所以，接下来的时间里会从最基础开始学起，每天一点一点的积累，希望能有所收获，加油，为自己加油。

 

二分法查找

这个方法最常用于猜数字游戏中，比如同伴预先指定一个1～100之间的数字，要你去猜这个数字是多少，当你猜一个数字之后，你的同伴会告诉你这个数字是大了还是小了或者说猜对了，如果你采用乱蒙的方式，或者采用线性查找的方式，也许你运气很好，会一次或者两次猜中，但是如果运气很差的话就不能保证了。而采用二分法查找的方式猜1～100之间的数字，你最多猜7次就能完成，这就是二分法的优势，具体的代码实现如下。

public int myFind(int searchKey){
	int min  = 0; 
	int max = nElems - 1;//nElems 数组的长度
	int current ;
	while(true){
		current = (min + max)/2;
		//a为 int[] 数组	
		if(a[current] == searchKey){
			return current; //返回当前的下标值
		}else if(min>max){
			return nElems; //如果min大于了max证明没有查找到，则返回数组长度
		}else if(a[current] >searchKey){
			max = current-1;
		}else if(a[current] <searchKey){
			min = current+1;
		}
			
		}
	}

 当然这样做的前提是该数组是有序数组，如果没有经过排序的数组这样操作，结果是可想而知的。

 

另外有序数组采用二分法查询效率很高，但是删除插入很慢，因为要删除和插入会使删除和插入数据的后面需要移动。

 

再另：二分法在数组长度较短的时候可能体现不出优势，但是当数组长度越长的时候他的优势越明显。比如0～1000，如果是线性查找的话是500次，而二分法查找则最多只需要10次。10000是14次，100000是17次……至于这最多次数是怎么算出来的，大家可以想想我们怎么查找的。我们是按2的n次幂进行查找的，2的7次幂是128，2的10次幂是1024……。OK，现在大家应该明白二分法查找的效率在数组长度越长的时候的效率越高的原因了吧，嘿嘿，抛砖引玉

 

 

再再另：数组的缺点：大小在初始化的时候就固定了，如果数据没有超过数组的大小，则出现空间浪费，如果超过了又会内存溢出；有序数组查询快速，但插入和删除又慢；无序数组插入快，但查找慢，这些都是数组的一些缺点。

 

 

看了的觉得很小儿科的请手下留情，如有不足请指正，谢谢

(参考《Java数据结构和算法》)