二分搜尋法（Binary Search）完整教學（三）有相同值的情境
二分搜尋法（Binary Search）完整教學（三）

含有重複值的情境

在上一篇中我們留下了一個重大問題，是時候來討論了。

問題

如果 array 裡面有重複值，要尋找的 target 就可能有多個答案，那我們該回傳哪一個？可以看以下例子

跟以前一樣，解決問題的第一步，是給問題一個明確的定義。其實我們通常在意的，會是最前面一個，或是最後面一個，中間的通常不是那麼在意，或說，只要能找到最前與最後，中間也就不困難了。因此，我們定義出以下兩個新需求，並且要想辦法達成。

在 array 中，找到 >= target 的元素裡面，最小的那個的 index 在 array 中，找到 > target 的元素裡面，最小的那個的 index

仔細想想這兩個新定義的需求，第一個情境，當找到多個等於 target 的元素時，會取到最左邊的那個，而第二個情境，則會取到最右邊的下一個，如果想要最右邊就 -1 即可，為什麼要這樣定義，下面會解釋。至於找不到的狀況，則跟前篇文章做一樣的事，這裡不再贅述。參考以下圖解。

至於如何實作，答案其實與之前非常類似，想挑戰的朋友可以先不要往下看，試著自己動手調整看看，提示是：想清楚當 nums[mid] == target 時該做什麼即可。

解答

在 array 中，找到 >= target 的元素裡面，最小的那個的 index

int binary_search_left(vector<int> &nums, int target) {

int left = 0;

int right = nums.size() - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (nums[mid] >= target) {

right = mid - 1;

} else if (nums[mid] < target) {

left = mid + 1;

}

}

return left;

} int main() {

vector<int> nums = {1,3,4,4,4,7,8}; cout << binary_search_left(nums, 3) << endl; // 1 <- 找到，回傳 index cout << binary_search_left(nums, 4) << endl; // 2 <- 找到，回傳最左邊的 index cout << binary_search_left(nums, 5) << endl; // 5 <- 找不到，但回傳 >= 他的裡面，最小的元素 index cout << binary_search_left(nums, 11) << endl; // 7 <- 同上，雖超出最大 index 範圍，卻是合理的

}

註：由於只剩兩種情境，第二個判斷式可以直接簡化成 else {…}，但在此為了方便閱讀理解，把詳細條件寫出來了。

有沒有發現，幾乎就只是拿掉 nums[mid] == target 時 return mid 的情境而已，因為關鍵就在於我們不要一找到就 return 結果，不然我們很可能就會 return 了中間某個點，而找不到最左邊的那一個。所以問題就剩下：

當 value 等於 target 的時候我們到底該做什麼 ?

答案也很簡單，因為我們現在要找最左邊，所以很自然的，當找到 nums[mid] == target 的時候，由於我們還不確定是否為最左，於是我們繼續把 right 的位置減小，讓 right = mid-1，最終，和之前一樣我們會走到 left == right 的那一刻，此時有兩種可能

left 與 right 都停留在我們要的，等於 target 的所有位置中，最左邊的那個 index，如下圖情境。

2. 再更左邊一格，如下圖情境。（假如一開始 nums 就只有 6 個元素）

但不論哪種情況，最終下一步 left 都會停在我們的答案上面（跟上篇一樣的道理，試著想清楚這點很重要），結束整個 binary search 並回傳答案。至於 left 與 right 都在右邊？不會有這個情境出現的，讀者們也可以自行想想為何如此。

現在來看看，另一個非常像的問題該怎麼辦

在 array 中，找到 > target 的元素裡面，最小的那個的 index

int binary_search_right(vector<int> &nums, int target) {

int left = 0;

int right = nums.size() - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (nums[mid] > target) {

right = mid - 1;

} else if (nums[mid] <= target) {

left = mid + 1;

}

}

return left;

} int main() {

vector<int> nums = {1,3,4,4,4,7,8}; cout << binary_search_right(nums, 3) << endl; // 2 <- 找到，回傳最右邊的 index + 1 cout << binary_search_right(nums, 4) << endl; // 5 <- 找到，回傳最右邊的 index + 1 cout << binary_search_right(nums, 5) << endl; // 5 <- 找不到，但回傳 > 他的裡面，最小的元素 index cout << binary_search_right(nums, 11) << endl; // 7 <- 同上，雖超出最大 index 範圍，卻是合理的

}

非常小的改動即可完成，只是把第一個判斷情境的 >= 改成 > 而已。注意，因為他回傳的是最右邊的 index+1，所以即使元素只有一個，他回傳的 index 仍然是該位置 +1，實際使用時可以看狀況自行 -1 調整回原位，因為這樣程式碼寫起來比較方便，跟前面的問題可以清楚的對照比較，細節的證明也幾乎一樣，有興趣的可以自己想想看。另外，如果想做到直接輸出最右邊的位置（而不是最右邊 +1）也是做得到的，有興趣的也可以試試看當思考練習。
['Ding-Chi Lin']
['Python', 'Binary Search', 'Programming', 'Software Development', 'Algorithms']