面試題:竟然有90%的程序員不能把這個(gè)算法完全寫正確肖方。。未状。

前幾天俯画,在論壇上看到有統(tǒng)計(jì)說有90%的程序員不能夠?qū)憣唵蔚亩址ā6址ú皇呛芎唵蔚膯幔?這難道不是聳人聽聞司草?

學(xué)習(xí)Python中的小伙伴艰垂,需要學(xué)習(xí)資料的話,可以前往我的微信公眾號(hào):速學(xué)Python埋虹,后臺(tái)回復(fù):簡書猜憎,即可拿Python學(xué)習(xí)資料

這里有我自己整理了一套最新的python系統(tǒng)學(xué)習(xí)教程,包括從基礎(chǔ)的python腳本到web開發(fā)搔课、爬蟲胰柑、數(shù)據(jù)分析、數(shù)據(jù)可視化爬泥、機(jī)器學(xué)習(xí)等柬讨。送給正在學(xué)習(xí)python的小伙伴!這里是python學(xué)習(xí)者聚集地袍啡,歡迎初學(xué)和進(jìn)階中的小伙伴踩官!

其實(shí),二分法真的不那么簡單境输,尤其是二分法的各個(gè)變種蔗牡。 最最簡單的二分法,就是從一個(gè)排好序的數(shù)組之查找一個(gè)key值嗅剖。 如下面的程序辩越。

這個(gè)程序,相信只要是一個(gè)合格的程序員應(yīng)該都會(huì)寫信粮。 稍微注意一點(diǎn)黔攒, 每次移動(dòng)left和right指針的時(shí)候,需要在mid的基礎(chǔ)上+1或者-1蒋院, 防止出現(xiàn)死循環(huán), 程序也就能夠正確的運(yùn)行莲绰。

但如果條件稍微變化一下欺旧, 你還會(huì)寫嗎?如蛤签,數(shù)組之中的數(shù)據(jù)可能可以重復(fù)辞友,要求返回匹配的數(shù)據(jù)的最小(或最大)的下標(biāo);更近一步称龙, 需要找出數(shù)組中第一個(gè)大于key的元素(也就是最小的大于key的元素的)下標(biāo)留拾,等等。 這些鲫尊,雖然只有一點(diǎn)點(diǎn)的變化痴柔,實(shí)現(xiàn)的時(shí)候確實(shí)要更加的細(xì)心。 下面列出了這些二分檢索變種的實(shí)現(xiàn)疫向。

1咳蔚、找出第一個(gè)與key相等的元素

2、找出最后一個(gè)與key相等的元素

3搔驼、查找第一個(gè)等于或者大于Key的元素

4谈火、查找第一個(gè)大于key的元素

5、查找最后一個(gè)等于或者小于key的元素

6舌涨、查找最后一個(gè)小于key的元素

接下來糯耍,大家可以對這四種變種算法進(jìn)行相應(yīng)的測試。

很多的時(shí)候囊嘉,應(yīng)用二分檢索的地方都不是直接的查找和key相等的元素温技,而是使用上面提到的二分檢索的各個(gè)變種,熟練掌握了這些變種哗伯,當(dāng)你再次使用二分檢索的檢索的時(shí)候就會(huì)感覺的更加的得心應(yīng)手了荒揣。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市焊刹,隨后出現(xiàn)的幾起案子系任,更是在濱河造成了極大的恐慌,老刑警劉巖虐块,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件俩滥,死亡現(xiàn)場離奇詭異,居然都是意外死亡贺奠,警方通過查閱死者的電腦和手機(jī)霜旧,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來儡率,“玉大人挂据,你說我怎么就攤上這事《眨” “怎么了崎逃?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長眉孩。 經(jīng)常有香客問我个绍,道長勒葱,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任巴柿,我火速辦了婚禮凛虽,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘广恢。我一直安慰自己凯旋,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布袁波。 她就那樣靜靜地躺著瓦阐,像睡著了一般。 火紅的嫁衣襯著肌膚如雪篷牌。 梳的紋絲不亂的頭發(fā)上睡蟋,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音枷颊,去河邊找鬼戳杀。 笑死,一個(gè)胖子當(dāng)著我的面吹牛夭苗,可吹牛的內(nèi)容都是我干的信卡。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼题造,長吁一口氣:“原來是場噩夢啊……” “哼傍菇!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起界赔,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬榮一對情侶失蹤丢习,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后淮悼,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體咐低,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年袜腥,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了见擦。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡羹令,死狀恐怖鲤屡,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情福侈,我是刑警寧澤酒来,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站癌刽,受9級(jí)特大地震影響役首,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜显拜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一衡奥、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧远荠,春花似錦矮固、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至邻梆,卻和暖如春守伸,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背浦妄。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來泰國打工尼摹, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人剂娄。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓蠢涝,卻偏偏與公主長得像,于是被迫代替她去往敵國和親阅懦。 傳聞我的和親對象是個(gè)殘疾皇子和二,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容