Binary Search (1) – 陪你刷題

Binary search 是一種在有序陣列做搜尋的演算法,其時間複雜度為 O (log n) 對數時間,相當高效。

Binary search 框架

以下是 binary search 的框架,但只適用於有序且不重複的 Array :

int bsearch(vector<int>& a, int value) {
    int low = 0;
    int high = a.size()-1;

    while (low <= high) {
        int mid = low + ((right-low)>>1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else if (a[mid] > value) {
            high = mid - 1;
        }
    }
    return -1;
}

3個實作上容易犯的錯誤:

閱讀全文〈Binary Search (1) – 陪你刷題〉