→ FRAXIS: 按這樣實作法 怎麼實現 C++ 的 lower_bound?時間要O(lg n) 08/07 21:27
謝謝F大的提醒！！！這篇真是獻醜了，我還真的沒想過這樣會讓複雜度變成 O(n)，
想說學校這樣教、我就這樣理解，果然人還是有盲點的。
剛剛稍微分析了一下，假設把最後線性查找的部分再改為二次 binary search，
那複雜度變成 lgn + lg(n/2) + lg(n/4) + lg(n/8) + ......
= lgn + (lgn-1) + (lgn-2) + (lgn-3) + ......
= lgn + klgn - k(k+1)/2 // 然後假設最多重複查找 k = lgn 次
= lgn + lgnlgn - 0.5lgn(lgn+1)
= 0.5(lgnlgn + lgn)
如此一來，雖然比原生的 lgn 要慢，但是還是比一律線性查找的 O(n) 要快得多
-----------------------------------------------------------------------
至於原 PO 所提到何時 high=mid、何時 high=mid-1 的問題，我認為就是搭配 while
迴圈來看，只要確保每次迭代都至少能減少一個 problem size 為原則即可。
我有時間再來詳細看看新版本的 binary search 要怎麼理解比較好，寫成新的投影片之後
再貼上來。
https://stackoverflow.com/questions/6443569/implementation-of-c-lower-bound
(最下面的 code 是本次重點)
而這篇文有警惕意味，所以會留著不會刪文。
※ 編輯: alan23273850 (1.168.85.29), 08/07/2017 23:29:17
→ FRAXIS: 而且你的 binary search 是 3-way branch 08/08 08:07
→ FRAXIS: 實際上會比 2-way branch 來的慢 08/08 08:08
推 shaopin: 不是只要在corner case上注意一下就可以變成lower or upp 08/08 09:43
→ shaopin: er bound了嗎? 08/08 09:43
※ 編輯: alan23273850 (1.165.79.66 臺灣), 05/09/2020 23:38:27