文章目录
二分查找（Java实现）算法思想算法描述代码参考运行时间
二分查找（Java实现）
算法思想
二分查找是一种非常高效的算法，又称之为折半查找。其前提条件为其查找的序列必须是有序的序列。
算法描述
计算出整个查找区间的中间位置mid=low+(high-low)/2;(可以防止溢出)用待查关键字值与中间位置关键字值进行比较；若相等，则查找成功；若大于，则在后半个区域中继续进行折半查找。若小于，则在前半个区域中继续进行折半查找。 查找成功，返回关键字所在数组下标，没找到返回-1；
代码参考
public class BinarySearch {
public static int rank(int key,int[] arr){//静态方法
int low=0;
int high=arr.length-1;
while(low<=high){
int mid=low+(high-low)/2;//防止溢出
if(arr[mid]>key){
high=mid-1;
}
else if(arr[mid]<key){
low=mid+1;
}
else
return mid;
}
return -1;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("请输入数组的个数：");
int lengthOfArr=sc.nextInt();
System.out.println("请输入数组：");
int[] a=new int[lengthOfArr];
for (int i = 0; i <lengthOfArr; i++) {
a[i]=sc.nextInt();
}
Arrays.sort(a);//排序
System.out.println(Arrays.toString(a));//输出数组
System.out.println("请输入要查找的key值");
int key=sc.nextInt();
System.out.println(rank(key,a));
}
}
运行时间
时间复杂度：O(log2n) 时间复杂度即while循环的次数。 二分查找每次排除掉一半的不适合的值，最坏情况下是在排除到只剩下最后一个值之后得到结果，依次是n,n/2,n/(2)2,…n/(2)m。(操作进行了m次)
n/(2)^m=1 是n,n/2,n/(2)2,…n/(2)m。(操作进行了m次)
n/(2)^m=1 即2^m=n ，所以log2n=m.时间复杂度是O(log2n)。
