算法回顾之三：二分查找

算法回顾系列第三篇：二分查找算法

------------------------------------------------

二分查找算法

基本原理：

首先,假设表中元素是按升序排列.

将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功.

否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.

重复以上过程(使用递归),直到找到满足条件的记录,使查找成功,或直到子表不存在为止.

程序实现：

/**
    * 二分查找 
    * @param input 已排序的待查数组.
    * @param target 需要插入的数.
    * @param from 当前数组查找范围的起点(0).
    * @param to 当前数组查找范围的终点(length-1).
    * @return 返回目标在数组中，按顺序应在的位置.       
    */
    private static int binarySearch(int[] input, int target, int from, int to){
    	int range = to-from;//如果范围大于0，即存在两个以上的元素(子表)，则继续拆分
    	if(range > 0){
    		//选定中间位
    		int mid = (to+from)/2;
    		//如果临界位不满足,则继续二分查找 
    		if (input[mid] > target){//中间位置的元素值大于目标元素(改为小于代表逆序)
    			return binarySearch(input,target,from,mid-1);//在0至中间位置查找
    		}else{//中间位置的元素值小于目标元素
    			return binarySearch(input,target,mid+1,to);//在中间位置到末尾位置查找
    		}
    	}else{
          	if (input[from] > target){//改为小于代表逆序
          		return from;
          	}else{
          		return from + 1;
          	}
    	}
    }

优点:比较次数少,查找速度快,平均性能好.

缺点:要求待查表为有序表,且插入删除困难.

二分查找方法适用于不经常变动而查找频繁的有序列表.