簡介

Binary Search是十分常用的演算法，在許多程式語言中都是陣列或列表的標準函數。以下程式碼整理自OpenJDK :

int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        if (midVal < key) // key在右邊
            low = mid + 1;
        else if (midVal > key) // key在左邊
            high = mid - 1;
        else // key在中間
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

除了學習演算法的運作原理之外，還要其他要點

• 題目有時需要改變搜尋條件
• 題目有時需要用到找不到key時的插入位置

---

解題範例

33. Search in Rotated Sorted Array

這一題很明顯是Binary Search的變形，只是差在陣列有被旋轉過，所以搜尋條件需要調整，先仿照本來的寫法再根據題意修改 :

public int search(int[] a, int key) {
    int n = a.length;
    if (n == 0) return -1; // 根據題意
    if (n == 1) return a[0] == key ? 0 : -1; // 根據題意
    
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        if (midVal < key) // 可能出錯
            low = mid + 1;
        else if (midVal > key) // 可能出錯
            high = mid - 1;
        else // 可能出錯
            return mid;
    }
    return -1; // 根據題意
}

當然這樣的程式是錯的，原因是已經排序好的陣列才適用Binary Search，而本題的陣列被破壞過一次，只有部分是有序的。因此我們需要在一邊執行演算法的同時，一邊檢查排序是否被破壞並進行修正。

而由於陣列的排序只被破壞一次，因此每次二分查找時，左右其中一邊一定是有序的，我們的目標會變成，只在確認目標值屬於有序的那一邊時，才按照本來的條件執行，否則就去找另一邊。注意左邊是小於等於中間值；右邊是大於中間值 :

public int search(int[] a, int key) {
    int n = a.length;
    if (n == 0) return -1;
    if (n == 1) return a[0] == key ? 0 : -1;
    
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        if (a[mid] == key) return mid; // 失去二分查找特性，因此在判斷哪邊
                                       // 有序之前，先檢查中間值
        if (a[low] <= a[mid]) // 左邊有序
            if (a[low] <= key && key < a[mid]) // 且key在左邊
                high = mid - 1; // 照舊
            else
                low = mid + 1; // 找另一邊
        else // 右邊有序
            if (a[mid] < key && key <= a[high]) // 且key在右邊
                low = mid + 1; // 照舊
            else
                high = mid - 1; // 找另一邊
    }
    return -1;
}

74. Search a 2D Matrix

本題更加單純，本質上只是把有序的陣列排成矩陣格式，因此只要在取值時轉換索引即可 :

public boolean searchMatrix(int[][] a, int key) {
    int h = a.length; // 取得矩陣大小
    int w = a[0].length;

    int n = h * w;
    if (n == 0) return false; // 根據題意
    if (n == 1) return a[0][0] == key; // 根據題意

    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int y = mid / w; // 計算mid索引的y軸
        int x = mid % w; // 計算mid索引的x軸
        int midVal = a[y][x]; // 取矩陣取得中間值
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return true;
    }
    return false;
}

81. Search in Rotated Sorted Array II

本題與33. Search in Rotated Sorted Array類似，差別在於陣列的內容並非嚴格遞增的，因此不能用二分法判斷左右哪一邊有序，所以需要先額外判斷無法判斷的狀況，並把左右翻犯縮減，然後再次搜尋 :

public boolean search(int[] a, int key) {
    int n = a.length;
    if (n == 0) return false; // 根據題意
    if (n == 1) return a[0] == key; // 根據題意

    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        if (a[mid] == key) return true;
        if (a[low] == a[mid] && a[mid] == a[high]) { // 額外判斷
            ++low; // 無法判斷是否有序
            --high; // 只能左右減一縮小範圍
        } else {
            if (a[low] <= a[mid]) { // 左邊有序
                if (a[low] <= key && key < a[mid]) { // 且key在左邊
                    high = mid - 1; // 照舊
                } else {
                    low = mid + 1; // 找另一邊
                }
            } else {
                if (a[mid] < key && key <= a[high]) { // 且key在右邊
                    low = mid + 1; // 照舊
                } else {
                    high = mid - 1; // 找另一邊
                }
            }
        }
    }
    return false;
}

153. Find Minimum in Rotated Sorted Array

本題在二分查找時的目標從特定值變成最小值。當中間值小於右側值時表示可能為小值，且右邊不再需要搜尋。中間值大於右側值表示非最小值，且左側不再需要搜尋。

public int findMin(int[] a) {
    int low = 0;
    int high = a.length - 1;
    while (low < high) { // 由於high縮減時為mid，左右側不可能重和
        int mid = (low + high) >>> 1;
        if (a[mid] < a[high]) { // 最小值不再右右側
            high = mid; // 可能是最小值
        } else {
            low = mid + 1;
        }
    }
    return a[low];
}

162. Find Peak Element

本題與153. Find Minimum in Rotated Sorted Array類似，都是改變搜尋目標，假如右側數值較低的話，那封值就應該在左側，反之亦然 :

public int findPeakElement(int[] a) {
    int low = 0;
    int high = a.length - 1;
    while (low < high) {
        int mid = (low + high) >>> 1;
        if (a[mid + 1] < a[mid]) { // 右側較低
            high = mid; // 峰值在左側
        } else {
            low = mid + 1;
        }
    }
    return low;
}