java实现折半查找

package althorgrim;
/**
* 1、必须采用顺序存储结果
* 2、关键字必须有序
* @author hanrk-2734
*
*/
public class TestBinarySearch {

public static int binarySearch(int a[],int goal){
int high=a.length-1;
int low=0;
while (low<=high) {
int middle=(low+high)/2;
if (a[middle]==goal) {
return middle;
}
else if (a[middle]>goal) {
high=middle-1;
}
else {
low=middle+1;
}
}
return -1;

}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] src = new int[] {1, 3, 5, 7, 8, 9};
System.out.println(binarySearch(src, 3));
}

}
O（1）：直接寻址到

O（n）：遍历n个元素

O（logn）：随着元素增加，呈现指数关系

O（n2）：增加一倍元素，时间增加4倍

折半查找的算法时间复杂度最好的情况是O(1),平均情况下是logn。

分析一下，折半查找的算法时间复杂度为什么是logn？

算法的时间复杂度取决于运算时间，折半查询中主要依赖while循环次数，那么while循环次数是多少？假设有16个元素的数组进行折半查询，查询元素13

如果是n个元素，那么就是：

可以得出 k=logn

public class Demo {

public static void main(String[] args) {
int[] array = new int[] {3,6,8,9,10,11,13,19,25};
//声明角标最小和最大角标和折半角标
int min=0;
int max=array.length-1;
int mid=(max+min)/2;
//声明要查找的值
int key=13;
//循环查找循环里肯定要折半的操作
//我现在已经明确知道循环什么时候停止
//使用 key 和中间角标的值比较如果相等循环停止

while(key!=array[mid]) {
if(key>array[mid]) {
min=mid+1;
}else if(key<array[max]){
max=mid-1;
}
//重复折半的操作
mid=(max+min)/2;

//如果数组中没有这个数会造成死循环
//需要一个出口让程序停止
if(min>max) {

//这里说明没找到这个数需要停止循环
mid=-1;
break;
}
}System.out.println("坐标是："+mid);

}

巴特西

java实现折半查找

最新文章

热门文章