蜜桃视频91,怡红院爽妇网,黄片网在线,日韩城人免费,欧美色图365,中日欧美中文字幕第一页,回本Aa一级黄色视屏,无码V∧

如果你想腳踏實地的學好算法，那么就從這篇文章開始，從最基礎(chǔ)的二分查找開始，真正的掌握好基礎(chǔ)算法，為未來的轉(zhuǎn)型打下堅實的基礎(chǔ)。這篇文章來自承志兄，對二分查找寫的入木三分，強烈推薦！

歡迎加我微信，我會定期在朋友圈里發(fā)放這種干貨總結(jié)，精華文章，讓你快人一步打好算法根基：

? 1??

二分法可以說是鼎鼎大名，哪怕是沒有學過編程的同學，也許說不上來二分法這個名字，但是對于其中的精髓應(yīng)該都是有所了解的。不了解的同學也沒關(guān)系，我一句話就能交代清楚：我們每次將一個集合一分為二，每次舍棄其中一半。

早在兩千多年前，莊子就搞清楚了二分法的精髓，他說：一尺之棰，日取其半，萬世不竭。從這個角度來說，二分法可能是這個世界上最古老的算法之一了。

二分法不僅古老，而且在計算機系統(tǒng)當中非常常見，許多系統(tǒng)當中都用到了二分法的思想。除此之外，在面試的時候，二分法的算法題也是?？?。因為二分法本身不復雜，幾乎人人都會，但是對二分法的使用能力卻各有不同。出二分法的題，可以真實考察面試者的算法能力和編程功底。

不說比較困難的算法題想不出思路，就說最簡單沒有任何難度的純二分，在面試的時候，出錯的寫出bug的也大有人在。

很多人會覺得奇怪，二分法這么簡單的算法，真的有人寫不出來嗎？

還真的有，原因也很簡單，恰恰就是二分法太簡單了。

無論是在算法導論還是在一些其他的算法教材當中，關(guān)于二分法的描述都不多，詳細的會有一些圖例展示一下二分法的思想，簡單的就用幾句話描述一下原理，最后再展示一下代碼，就完事了。讀者在學的時候也是一樣，看了一眼原理，哦，非常簡單，再看一眼代碼，只有三四行，差不多一眼就能記住，那就丟在一邊吧。到了真正上手的時候，問題一下就暴露了出來。

二分法最常見的問題有兩個，一個是二分的區(qū)間邊界不清楚，另一個是二分查找的結(jié)果不明確。我想，這兩個問題是前幾次實現(xiàn)二分法的時候，一定會遇到的。遺憾的是，目前的教材當中對于這兩個問題介紹都不多，都只有代碼，留給讀者自行揣摩。

? 2??

我們先說第一個問題——邊界

早在小學我們就學過，用l表示區(qū)間左邊界，r表示區(qū)間右邊界，mid=(l + r) / 2表示二分的中間點。這個在數(shù)學里非常明確，但在編程的時候，有一個隱藏的問題被忽略了。究竟這個區(qū)間是閉區(qū)間呢，還是開區(qū)間呢，還是半開半閉區(qū)間或者是半閉半開區(qū)間？如果這個問題不想清楚，想要一次性寫出沒有bug的代碼，老實說很不容易。

首先，二分終止的條件究竟怎么寫，是while (l < r) 還是 while (l <= r) 還是別的？還有，在搜索的時候，我們究竟要不要將a[mid] == v的情況單獨判斷？我們是判斷a[mid] < v還是a[mid] <= v？假設(shè)我們選擇用a[mid] <= v，得到的結(jié)果為true。我們知道答案應(yīng)該在區(qū)間的右半邊，我們需要舍棄左邊的區(qū)間。應(yīng)該對l賦值，但是我們是賦值成l = m呢還是l=m + 1呢？又是為什么呢？

你看，如果l和r表示的區(qū)間不考慮清楚，我們在實際寫代碼的時候就會遇到這樣棘手的問題。坑爹的是，當我們?yōu)檫@些邊界頭疼的時候，我們并不能意識到這是因為我們沒有搞清楚表示區(qū)間的方法導致的。往往會覺得是自己不夠熟悉。

顯然，要解決這個問題需要確定l和r表示的區(qū)間種類。那么到底應(yīng)該選擇什么區(qū)間呢？是左閉右開，還是全閉，還是左開右閉呢？

答案有點出人意料，都行。

理論上來說，不論選什么樣的區(qū)間，只要代碼得當，都是可以的，可以說是完全看個人喜好。不過我個人推薦左閉右開，原因很簡單，這個和編程當中的數(shù)組定義的情況一致。我們都知道，在代碼的世界里，數(shù)組是從0開始的，一個長度為10的數(shù)組，最后一個元素的下標是9。如果使用左閉右開區(qū)間，我們將l=0，r=數(shù)組長度，就完成了初始化，如果用閉區(qū)間，r=長度-1，不免顯得有些多余。

假設(shè)我們確定了使用左閉右開區(qū)間，我們再來看前面說的兩個問題。

區(qū)間確定了，終止條件也就明確了，左閉右開區(qū)間[l, r)不為空的話，r 至少大于等于l + 1。我們要在區(qū)間長度大于1的時候執(zhí)行二分，所以二分的循環(huán)條件應(yīng)該是while (l + 1 < r)。

? 3??

那么while里的判斷條件呢？

我們列舉一下，a[mid] 和v的大小關(guān)系無非只有三種。

第一種a[mid] = v，很簡單，mid就是我們要查找的結(jié)果，直接返回。

第二種a[mid] < v，說明我們應(yīng)該取右邊的區(qū)間，由于l的位置可以取到，而mid已經(jīng)不是答案了，所以l = mid + 1。

第三種a[mid] > v，應(yīng)該取左邊的區(qū)間，mid不是答案，但是由于r指向的位置本身就不在候選區(qū)間里，所以r = mid，而不是mid-1，因為mid-1可能是答案，而r處的位置是取不到的。

到這里，似乎一切完美，我們可以很順利地寫出代碼了。但是還沒有結(jié)束，依然還有一個小問題。

前文說了，a[mid]和v的關(guān)系有三種，當a[mid] = v的時候，我們就找到了答案。從這個角度來看，我們二分的時候，通過l和r縮小區(qū)間的范圍，通過mid來尋找答案。但是既然我們已經(jīng)折半?yún)^(qū)間的大小了，那么當區(qū)間長度為1的時候，剩下的就是答案，我們?yōu)槭裁催€需要通過mid去查找答案呢？如果我們就想通過區(qū)間本身來查找答案，那么應(yīng)該怎么辦呢？

也不難，我們需要把a[mid]小于和等于v的兩種情況合并，由于a[mid]可能等于v，所以我們不能跳過mid這個位置，l = mid + 1 應(yīng)該寫成l = mid，于是整個代碼也就出來了：

def?binary_search(a,?v):??
????l,?r?=?0,?len(a)??
????while?l?+?1?
????????m?=?(l?+?r)?//?2??
????????if?a[m]?<=?v:??
????????????l?=?m??
????????else:??
????????????r?=?m??
????#?通過a[l]?==?v判斷v不存在與a數(shù)組當中的情況??
????return?l??

? 4??

可能會有同學好奇，如果我不使用左閉右開，而使用閉區(qū)間呢，代碼又該怎么寫？

其實只要把區(qū)間想清楚了，寫出來也不難。

def?binary_search(a,?v):??
????l,?r?=?0,?len(a)?-?1??
????while?l?<=?r:??
????????m?=?(l?+?r)?//?2??
????????if?a[m]?==?v:??
????????????return?m??
????????if?a[m]?
????????????l?=?m?+?1??
????????else:??
????????????r?=?m?-?1??
????#?表示不存在??
????return?-1??

不過還有一個小問題，為什么閉區(qū)間形式的二分法的判斷推薦是while (l <= r)呢？換成while (l < r)行不行？這個問題就留給大家思考。

二分法雖然簡單，但這些細節(jié)都理解清楚也并不容易，在算法領(lǐng)域當中，如果細節(jié)沒有理解到位，陰溝里翻船是非常平常的事情。希望今天的文章能對大家有所幫助。

二分法，太容易寫出bug了！

二分法，太容易寫出bug了！