/**
*
*/
package arithmetic;
/**
* 二分查找, 要求：数据必须有序排列
*
* 设数据量为N,复杂度为:log2(N)
* 数据量翻倍时，复杂度加1，未翻倍时,倍数的临界会导致复杂度加1
*
* @author zhangkexing
*
*/
public class BinarySearch {
int postion = -1;
/**
*
* @param array 原始数组
* @param x 从数组中要查找的数字
* @return 返回查找几次
*/
public int binarySearch(int[] array,int x){
int step = 0;
int low = 0;
int hight = array.length -1;
while(low <= hight){
++ step;
postion = (low + hight) /2;
int data = array[postion];
System.out.println("search:"+x+" postion:"+postion+" low:"+low+" hight:"+hight);
if(data == x){
return step;
}else if(data > x){
hight = postion - 1;
}else{
low = postion + 1;
}
}
return -1;
}
public static void main(String[] args) {
int len = 2049;
int[] array = new int[len];
for(int i=0;i<len;i++){
array[i]=i;
}
int step = new BinarySearch().binarySearch(array, 70);
if(step == -1){
System.out.println("未查找到");
}else{
System.out.println("共执行"+ step+"次");
}
}
}
算法——二分查找
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
