二分法檢索(binary search)又稱折半檢索,二分法檢索的基本思想是設數組中的元素從小到大有序地存放在數組(array)中,首先將給定值key與數組中間位置上元素的關鍵碼(key)比較,如果相等,則檢索成功;否則,若key小,則在數組前半部分中繼續進行二分法檢索;若key大,則在數組後半部分中繼續進行二分法檢索。這樣,經過一次比較就縮小一半的檢索區間,如此進行下去,直到檢索成功或檢索失敗。

代碼示例:

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        int[] a={9,5,7,3,2,1,5,6,8,4};
        Arrays.sort(a);  //二分法查找之前,一定要對數組元素排序
        System.out.println(Arrays.toString(a));
        System.out.println(binarySearch(a,8));
    }

    public static int binarySearch(int[] a, int key){
        int low=0;
        int high=a.length-1;
        while (low<=high){
             int middle=(low+high)/2;
             if (key==a[middle]){
                 return middle;  //返回查詢到的索引位置
             }
             if (key>values[middle]){
                 low=middle+1;
             }
             if (value<values[middle]){
                 high=middle-1;
             }
        }
        return -1;  //上面循環完畢,説明未找到,返回-1
    }
}