二分法查找(折半检索)又叫binary search.
要在一堆数据中查找是否存在某一个已知数,二分法查找的步骤:
第一步,对数据实现排序
第二步,将该数与排序后的数据集的中间一个数进行比较
第三步,如果该数等于这个中间数,那就找到了,返回位置索引。
如果该数大于这个中间数,那么再对右边的数进行对半查找。
如果该小于这个中间数,那么再对左边的数进行对半查找。
重复第三步,直到找到为止。
示例代码:
import java.util.Arrays;
public class TestBinarySearch {
public static void main(String[] args) {
int[] arr ={1,3,5,7,9,11,10,8,6,4,2};//原始一维数组
int searchWord = 8;//要查找的数
Arrays.sort(arr);//先排序
System.out.println("排序后的数据是"+Arrays.toString(arr));
System.out.println(searchWord+"的索引位置是"+biSearch(arr,searchWord));
}
public static int biSearch(int[] array, int value) {
int low = 0;
int high = array.length - 1;
int i = 0;
while (low <= high) {
int middle = (low + high) / 2;
i=i+1;
System.out.println("第"+i+"次二分后,当前中间数是"+array[middle]);
if (value == array[middle]) {
return middle;
}
if (value > array[middle]) {
low = middle + 1;
}
if (value < array[middle]) {
high = middle - 1;
}
}
return -1;//找不到返回-1
}
}
运行结果: