二分搜尋法（Binary Search）完整教學（二）
找不到怎麼辦
在上一篇中我們留下了兩個問題，這篇先來討論第一個問題。
問題
往往我們無法真的找到 target，但我們還是想要一個最接近 target 的答案，那該怎麼辦呢？
定義
討論問題先從清楚的定義開始，是良好的習慣，先看一下以下例子。
- Nums: [1, 3, 4, 7, 8, 10]
- Target: 5
我們要找的 target 5 並不在 nums 裡面，但最接近的有兩個，分別是大於他的最接近的數 7 跟小於他的最接近的數 4。兩個目標不同，但其實我們會做一個就可以了，因為另一個一定就在旁邊。我們就來找大於他的裡面，最接近的那個位置吧。現在讓我們來重新定義一下想做的事：
目標：在 nums 中尋找 >= target 裡，最小的那個數的 index。
解法
如果你看懂了這個新的定義，先想像一下，這跟上一篇基礎問題的差別，只差在最後如果找不到，我們不要回傳 -1，而是回傳大於他的最接近的位置，應該很直覺得可以猜到，這個值大概會是 left 或 right 的最後位置對吧，但到底是誰呢？會不會又有 +1, -1 的問題呢？現在來搞清楚吧！
先給大家個選擇題挑戰看看，上面最後的 return 位置該填什麼？
A: left
B: right
C: left+1
D: right-1
如果答對了，恭喜你！答案意外的簡單，就是回傳 left 即可（選項 A），但為什麼呢？
來看看我們有哪些可能的情境，記得我們的 left 和 right 代表著可能含有答案的閉區間，對任何一個數字，假如一直找不到，這個區間會不斷減小，直到走到 left == right ，此時區間內只剩下 1 個數字了，所以本輪會得到最終結果。
而這個唯一的數字，根據 array 內容物和 target 不同，有可能最終大於、等於、或小於我們要找的 target。等於的話，這邊會直接結束，上一篇討論過了，以下討論大於跟小於。
大於的情境：
小於的情境：
註：只有 index 必須是正整數，target value 可以是任意浮點數值。
仔細觀察，會發現不管哪個情境，下一步都會讓 left 的位置停留在 >= target 的最小 value 的 index 上面，並且結束整個 binary search 流程。因為
- 如果大於 target，我們會讓 right = mid-1，而 left 不變（ left 繼續停留在我們想要的位置上）
- 如果小於 target，我們會讓 left=mid+1 而 right 不變。（剛好把 left 移到我們想要的位置上）
之後由於 left 與 right 已經交叉，binary search 迴圈正好結束。接著再來看一個比較特別的情境。
仔細觀察這個情況，最後由於 target 還是比較大，我們會再做一次 left = mid+1 才結束，如此最終停留的 left 位置會超出最大可能 index（剛好就是等於 array 的 length)，但這其實是正確的，記得我們要找的其實是 >= target 裡面，最小的可能位置，因為我們整個 array 通通沒有 >= target 的數，因此最終停留在超出 array 一格的位置。
最後，還有一種例外情境是，還走不到 left == right 就直接結束了，看以下例子：
剛好要找的位置，比當下的 left 還要小，而 right 又剛好在右邊一格，如此 mid 會在 left 的位置上，而下一步 right 一樣會移動到 left 左邊一格(mid-1)，導致迴圈直接結束，left 則依然停留在正確的位置上。
最後，看一下程式碼與輸出結果：
結語
我們終於處理好了找不到值的狀況了，除了上一篇給的問題外，許多實際題目都需要這個應用，如以下：
在一排價格已經排序好的商品中，找到所有小於某價錢的商品數量
不一定剛好有某件商品的價錢等於我們的目標價，但我們還是可以二分搜尋 >= 此價錢的商品們的最小 index，那他的左邊就全都是我們要的了，也就是答案等於最終回傳的 index。（稍微想一下 index 從 0 開始的特性）。
但有另一個更麻煩的問題來了，假如有一堆商品同價錢該怎麼辦？會不會出錯？其實是會的！所以我們將在下一篇來討論 array 有重複值該怎麼辦。
留給讀者的練習：你能不能造出一個有重複值的例子，讓上面這份程式碼出問題，也就是無法滿足我們上面定義的需求呢？
