二分搜的實作方式

各種二分搜的模式

如果是常常閱讀程式碼的人，在閱讀二分搜的時候肯定都遇過一個問題 : 為什麼每個人維護的 $left$ 和 $right$ 都不太一樣，有時候是 $left = mid$，有時候是 $left = mid + 1$，這其中又有什麼不同呢 ?

開區間與閉區間

在決定 $left$ 和 $mid$ 要怎麼維護之前，我們要先理解開區間和閉區間是什麼。

開區間

開區間指的是區間的邊界不被包含在區間內，符號上會表示成 $(a, b)$，集合內的點 $x$ 符合條件 $a < x < b$。

閉區間

開區間指的是區間的邊界不被包含在區間內，符號上會表示成 $[a, b]$，集合內的點 $x$ 符合條件 $a \le x \le b$。

二分搜終止條件

前面討論的區間就是為了定義二分搜的終止條件，以及如何維護 $mid$ 的值。首先，我們要先決定 $left$ 和 $right$ 分別代表的意義，以左閉右開的二分搜舉例，假設二分搜的目標是找到 $x$，既然是使用左閉右開的二分搜，所以我們要維護兩個區間 $[left,mid)$ 和 $[mid,right)$，一直到區間最後變成 $[x, x)$，因為這個區間會剛好只有 $x$ 一個元素或是完全沒有元素，換句話說維護到最後區間的內容可以被解讀為找到 $x$ 或是沒找到 $x$，也就是說 while 迴圈的條件為 while(left < right) 即可讓區間停在左閉右開的 $[x, x)$，並且最後的答案會是 $left$。

各種二分搜的範例程式碼

左閉右閉

// 假設陣列 array 有 n 個元素
// 左閉右閉最後維護的值為 [x, x]
int left = 0, right = n - 1;
bool check = false;
while (left <= right) {
	int mid = (left + right) / 2;
	if (array[mid] < key) {
		left = mid + 1;
    }
	else if (array[mid] > key) {
		right = mid - 1;
    }
	else if (array[mid] == key) {
		cout << "答案在第" << mid << "項";
        check = true;
        break;
    }
}
if (check == false) {
    cout << "答案不在陣列中";
}

左閉右開

// 假設陣列 array 有 n 個元素
// 左閉右閉最後維護的值為 [x, x)
int left = 0, right = n - 1;
bool check = false;
while (left <= right) {
	int mid = (left + right) / 2;
	if (array[mid] < key) {
		left = mid + 1;
    }
	else if (array[mid] > key) {
		right = mid - 1;
    }
	else if (array[mid] == key) {
		cout << "答案在第" << mid << "項";
        check = true;
        break;
    }
}
if (check == false) {
    cout << "答案不在陣列中";
}

半開半閉 (左開右開)

使用注意

因為答案可能是 $(x, x]$ 也可能是 $[x + 1, x + 1)$，使用者須根據情況決定使用 $left$ 或是 $right$。

// 假設陣列 array 有 n 個元素
// 左閉右閉最後維護的值為 (x, x)
int left = -1, right = n;
bool find = false;
while (left + 1 < right) {
    int mid = (left + right) / 2;
    if(ans == array[mid]) {
        cout << "答案在第" << mid << "項";
        find = true;
        break;
    }
    else if(ans < array[mid]) {
        right = mid;
    }
    else {
        left = mid;
    }
}
if (find == false) {
    cout << "答案不在陣列中";
}