我们演算法老师说过对於一些比较常用、有名的算法，通常已经有先人发展出漂亮的写法 我们的任务就是找出漂亮、优美的写法，理解它，然後背起来！ 虽然老师那个时候是拿 qsort 当例子，但是我想 binary search 也是一样的。 这是我去年复习的时候写的投影片中的其中一页： https://upload.cc/i1/2020/05/09/927SNu.jpg 我是觉得这样的写法还是比较好理解 至於遇到多重相同值元素时可以一直往前找，就能碰到第一个出现的元素， 相对地如果要最後一个元素就一直往後找就好！ 另外，我自己是感觉这种着名算法未必要很坚持的看懂其他人的写法， 因为这种小细节往往是会花最多时间的地方，其实只要自己会写、写得出来就好。 当然能快速看懂一个人的 code 是种超能力，但如果是为了训练这种能力而花时间 在这种小细节上，CP 值恐怕不高。(花太多时间，却只提升一点点能力) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.168.85.29 ※ 文章网址: https://webptt.com/cn.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