二分搜尋法（Binary Search）完整教學（三）
含有重複值的情境
在上一篇中我們留下了一個重大問題，是時候來討論了。
問題
如果 array 裡面有重複值，要尋找的 target 就可能有多個答案，那我們該回傳哪一個？可以看以下例子
跟以前一樣，解決問題的第一步，是給問題一個明確的定義。其實我們通常在意的，會是最前面一個，或是最後面一個，中間的通常不是那麼在意，或說，只要能找到最前與最後，中間也就不困難了。因此，我們定義出以下兩個新需求，並且要想辦法達成。
- 在 array 中，找到 >= target 的元素裡面，最小的那個的 index
- 在 array 中，找到 > target 的元素裡面，最小的那個的 index
仔細想想這兩個新定義的需求，第一個情境，當找到多個等於 target 的元素時，會取到最左邊的那個，而第二個情境，則會取到最右邊的下一個，如果想要最右邊就 -1 即可，為什麼要這樣定義，下面會解釋。至於找不到的狀況，則跟前篇文章做一樣的事，這裡不再贅述。參考以下圖解。
至於如何實作，答案其實與之前非常類似，想挑戰的朋友可以先不要往下看，試著自己動手調整看看，提示是：想清楚當 nums[mid] == target 時該做什麼即可。
解答
在 array 中，找到 >= target 的元素裡面，最小的那個的 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
非常小的改動即可完成，只是把第一個判斷情境的 >= 改成 > 而已。注意，因為他回傳的是最右邊的 index+1，所以即使元素只有一個，他回傳的 index 仍然是該位置 +1，實際使用時可以看狀況自行 -1 調整回原位，因為這樣程式碼寫起來比較方便，跟前面的問題可以清楚的對照比較，細節的證明也幾乎一樣，有興趣的可以自己想想看。另外，如果想做到直接輸出最右邊的位置（而不是最右邊 +1）也是做得到的，有興趣的也可以試試看當思考練習。
實戰練習
終於，我們處理完重複值的問題了，再來看一次上一篇提到的問題
在一排價格已經排序好的商品中，找到所有小於某價錢的商品數量
現在知道該怎麼做了吧？跟上篇一樣，我們要找的仍然是 >= 此價錢的商品們的最小 index。但這篇的解法才是完整且正確的。
同樣的，也可以拿 Leetcode 第 34 題 來練習看看
如果目前全部都有看懂，你已經可以解決一道 Medium 難度的問題啦，有沒有很有成就感呢？
結語
其實這篇提到的兩個解法，分別對應到許多程式語言都有提供的 Binary Search 工具，在 c 裡面，他們就是 lower_bound 與 upper_bound，在 python 裡面就是 bisect_left 與 bisect_right。假如你現在已經很清楚他們的性質了，需要時直接調用他們即可，這兩個往往也是我們真正在做 Binary Search 時最常使用的技巧。我們下一篇就來聊聊，內建函式是怎麼做的。
註：javascript 似乎沒有類似的工具，但現在你知道該怎樣自己打造了
本篇留給讀者的最後一個小測驗：上述價錢的題目，如果用內建函式，該用 lower_bound (bisect_left) 還是 upper_bound (bisect_right) 呢？動手試試看吧！
