Java 学习和实践笔记（51）：二分法查找（折半检索）

二分法查找（折半检索）又叫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
}}

运行结果：