我們演算法老師說過對於一些比較常用、有名的算法，通常已經有先人發展出漂亮的寫法 我們的任務就是找出漂亮、優美的寫法，理解它，然後背起來！ 雖然老師那個時候是拿 qsort 當例子，但是我想 binary search 也是一樣的。 這是我去年複習的時候寫的投影片中的其中一頁： https://upload.cc/i1/2020/05/09/927SNu.jpg 我是覺得這樣的寫法還是比較好理解 至於遇到多重相同值元素時可以一直往前找，就能碰到第一個出現的元素， 相對地如果要最後一個元素就一直往後找就好！ 另外，我自己是感覺這種著名算法未必要很堅持的看懂其他人的寫法， 因為這種小細節往往是會花最多時間的地方，其實只要自己會寫、寫得出來就好。 當然能快速看懂一個人的 code 是種超能力，但如果是為了訓練這種能力而花時間 在這種小細節上，CP 值恐怕不高。(花太多時間，卻只提升一點點能力) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.85.29 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1502084077.A.70A.html ※ 編輯: alan23273850 (1.168.85.29), 08/07/2017 19:58:12 謝謝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 ※ 編輯: alan23273850 (1.165.79.66 臺灣), 05/09/2020 23:38:27