二分法查询

原创
2017/06/22 11:05
阅读数 38

/** * 递归查询 * 大于等于0即表示存在,-1表示不存在 * param array 查询数组 * param low 最小边界 * param hight 最高边界 * param key 查询数值 * param */

   public int recursion(int[] array,int low,int hight,int key){
	int half = low+hight >>>1;
	if(low>hight || array[half]<array[low] || array[half]>array[hight] || array[low]>array[hight]){
		return -1;
	}else{
		if(key == array[half]){
			return half;
		}else{
			if(key > array[half]){
				return recursion(array,half+1,hight,key);
			}else{
				return recursion(array,low,half-1,key);
			}
		}
	}
}

/**
 * 非递归查询
 * 大于等于0即表示存在,-1表示不存在
 * param array 查询数组
 * param low 最小边界
 * param key 查询数值
 * return
 */

public int notRecursion(int[] array,int low,int key){
	int hight = array.length-1;
	while(low<=hight){
		int half = low + hight >>> 1;
		if(key == array[half]){
			return half;
		}else{
			if(key > array[half]){
				low = half + 1;
			}else{
				hight = half - 1;
			}
		}
	}
	return -1;
}


public void queryTest(){
	int[] array = {1,2,3,4,5,6,7,8,9,10};
	int key = 6;
	int result = recursion(array,0,array.length-1,key);
	System.out.println(result);
	int result2 = notRecursion(array, 0, key);
	System.out.println(result2);
}
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部