/*
折半查找,查找数组中的某个数是否存在于数组中,存在的话会存在在那个位置
*/
class ZheBanTest {
//定义一个函数,查找未知数是否存在于数组中,存在的话会在什么位置
public static int halfSearch(int[] arr, int key) {
//定义最小角标,最大角标和折中后角标
int min = 0, max = arr.length - 1, mid = (min + max) / 2;
//定义循环进行查找
while(key != arr[mid]) { //如果这个数不等于中间数,就一直循环下去
if(key > arr[mid]) //如果这个数大于中间数,最小值就为中间数加1
min = mid + 1;
else if(key < arr[mid])
max = mid - 1;
if(min > max) //假如最小值大于最大值了。就不在运行下去了,返回-1;
return -1;
mid = (max + min) / 2; //每次循环中间数必须做的运算,让中间数随时改变
}
return mid; //如果等于中间数就说明找到了。把找到的位置返回出去
}
//折半查找的第二种方法
public static int halfSearch_1(int[] arr, int key) {
//定义最大、最小和中间值
int min = 0, max = arr.length - 1, mid;
//定义循环查找
while(min <= max) {
mid = (min + max) / 2;
if(key > arr[mid]) {
min = mid + 1;
} else if(key < arr[mid]) {
max = mid - 1;
} else
return mid;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2,4,6,7,9,12,14};
int index = halfSearch_1(arr, 9);
System.out.print(index);
}
} |