Java實現二分法查找算法

[ 什麼是二分查找 ]

二分查找又稱為折半查找，該算法的思想是將數列按序排列，采用跳躍式方法進行查找，即先以有序數列的中點位置為比較對象，

如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。以此類推不斷縮小搜索范圍。

[ 二分查找的條件 ]

二分查找的先決條件是查找的數列必須是有序的。

[ 二分查找的優缺點 ]

優點：比較次數少，查找速度快，平均性能好；

缺點：要求待查數列為有序，且插入刪除困難；

適用場景：不經常變動而查找頻繁的有序列表。

[ 算法步驟描述 ]

① 首先確定整個查找區間的中間位置 mid = （min + max）/ 2

② 用待查關鍵字值與中間位置的關鍵字值進行比較：

i. 若相等，則查找成功；

ii. 若小於，則在前半個區域繼續進行折半查找；

iii. 若大於，則在後半個區域繼續進行折半查找；

③ 對確定的縮小區域再按折半公式，重復上述步驟。

④ 最後得到結果：要麼查找成功，要麼查找失敗。折半查找的存儲結構采用一維數組存放。

查看本欄目

[ Java實現 ]

public class BinarySearch {  
    public static int binarySearch(int[] arr, int target) {  
        if (arr != null) {  
            int min, mid, max;   
            min = 0; // the minimum index  
            max = arr.length - 1; // the maximum index  
            while (min <= max) {  
                mid = (min + max) / 2; // the middle index  
                if (arr[mid] < target) {  
                    min = mid + 1;  
                } else if (arr[mid] > target) {  
                    max = mid - 1;  
                } else {  
                    return mid;  
                }  
            }  
        }  
        return -1;  
    }  
          
    // test case  
    public static void main(String[] args) {  
        int[] arr = { 1, 2, 3, 5, 6, 7, 8, 9, 23, 34 };  
        System.out.println(binarySearch(arr, 5));  
        System.out.println(binarySearch(arr, 23));  
        System.out.println(binarySearch(arr, 0));  
        System.out.println(binarySearch(arr, 35));  
    }  
}