查找算法:二分(折半)查找
package com.Algorithm.Search_Sort;
import java.util.Arrays;
public class Search {
public int array[] = {12,45,22,41,100,72,65};
public int array1[] = {99,34,76,92,34,17,77,41,40,36,6};
//二分查找 or 折半查找
public void BinarySearch(int num){//只适用于升序数组
//对于无序数组要先进行排序
int arr[]=this.array1;
Arrays.sort(arr);
System.out.println("使用二分查找法的数组为:"+Arrays.toString(arr));
//设定查找的起始位置和终点位置下标
int start = 0,end = arr.length-1,mid;
//设置是否查找成功的标记:记录查找到的下标,值=位置-1
int index = -1;
//查找条件
while(start <= end){//次数必须要加上=号,加上才能比对相邻的两个数
mid = (start + end) / 2; //与 mid = (start + end) >>> 1;作用相同
//mid的显示次数为查找次数,7 < 8=2的3次方,7个数最多查找3次
System.out.println("mid"+mid);
if(num == arr[mid]){//查找成功
index = mid;
break;//找到之后就已经完成任务了,要跳出循环
}else if(num > arr[mid]){//从后半段数组继续进行查找
start = mid + 1;
}else{
end = mid - 1;
}
}// end while
if(index == -1){
System.out.println("查找失败,该数组中没有数字"+num);
}else{
System.out.println("查找成功,"+num+"在数组中的位置为"+(index+1));
}
}
public static void main(String[] args) {
Search s=new Search();
s.BinarySearch(99);
}
}
查找结果为:
比较次数:
计算公式:
当顺序表有n个关键字时:
查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b。
注意:a,b,n均为正整数。