前面有介紹用 dp 方式把這題給解了，但看一下 Related Topics 發現也可以用 Binary Search 求解，上網參考大神們的解法，感覺特別巧妙。因為這題可用 dp 和 Binary Search，也變成是一道高頻難題。 這邊記錄一下大神們的想法。
這題是 Google 面試題，在 Hide Hint 中表示可以使用 binary-search 解決，剛開始覺得蠻 tricky 的，但仔細思考會覺得 binary-search 很符合這題目。
前面有介紹了 Binary Search 的通用模板，但通用模板還是有缺點，就是要找的目標須在 array 範圍內，這樣才能定義 index。但很多時候題目並不會有一個準確的 array 被定義，還是需要了解各個模板才能比較好的去解答各式題目。
Binary-Search (二分搜尋法)，是一種針對已經排好序的區間內， O(logN) 的搜索方式。 Binary-Search 在處理邊界時很容易出錯。 基本上都是沒注意到兩大原則 :
- 每次都一定要縮減收所區域
- 每次縮減不能排除潛在答案
雖然淺顯易見，但實踐在寫的時候還是常常會寫出 bug 。