各種二分搜的模式#
如果是常常閱讀程式碼的人，在閱讀二分搜的時候肯定都遇過一個問題 : 為什麼每個人維護的 \(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 << "答案不在陣列中";
}
