算法-二分查找極其效率

算法說明

又叫折半查找，要求待查找的序列有序。

每次取中間位置的值與待查關鍵字比較；

如果中間位置的值比待查關鍵字大，則在前半部分循環這個查找的過程；

如果中間位置的值比待查關鍵字小，則在後半部分循環這個查找的過程。

直到查找到了為止，否則序列中沒有待查的關鍵字。

示例代碼

/**
 * 二分查找算法實作，傳回查找資料在數組的序号。
 * @param array 資料
 * @param num 需要查詢的資料
 * @return 資料序号
 */
public static int biSearch(int[] array, int num) {
    int start = 0;
    int end = array.length - 1;
    int mid;
    while(start <= end) {
        mid = (start + end) / 2;
        if(array[mid] == num) {
            return mid;
        } else if(array[mid] < num) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}           

調用示例：

public static void main(String[] args) {
    int[] array = { 1, 2, 4, 6, 8, 9, 10, 11, 12, 34, 55};
    int biSearch = biSearch(array, 9);
    System.out.println(biSearch);
}           

算法複雜度

因為二分查找是一半一半的找，是以每次查找之後都會把查找範圍減半；

比如說在一個 1 - 8 的有序數組裡面查找 8 也就是查找最壞情況。

在數組當中完成二分查找需要 log2n - 1 次；

也就是時間複雜度是 log2n （就是 log 以 2 為底 n 的對數）