1.簡(jiǎn)單查找和二分查找

什么是簡(jiǎn)單查找呢纠亚,就是給一個(gè)數(shù)組吉嚣,挨個(gè)找一遍,看看自己要找的數(shù)在不在這個(gè)數(shù)組里面刘绣,或者在這個(gè)數(shù)組的哪個(gè)位置玖像。如果這個(gè)數(shù)組的長(zhǎng)度為 100,那么最壞的情況,也就是剛好找到最后一個(gè)才找到那個(gè)數(shù)捐寥,需要找 100 次笤昨。最好的情況下,第一個(gè)數(shù)剛好就是我們要找的握恳,這時(shí)只需找 1 次瞒窒。但是在正常情況下,我們的運(yùn)氣不可能總那么好乡洼,也不會(huì)總那么壞崇裁,所以就需要一個(gè)指標(biāo)來(lái)衡量這種查找的效率是怎樣的。

一般來(lái)說束昵,在算法中拔稳,我們使用 大O 來(lái)表示某種算法的速度,準(zhǔn)確的說是一種增速锹雏,就是隨著數(shù)據(jù)越來(lái)越多的情況下巴比,所需要的時(shí)間是怎樣變化的。

像這種簡(jiǎn)單查找礁遵,用 大 O 表示法就可以寫成 O(n) 轻绞。

那么二分查找又是什么呢,還是一個(gè)數(shù)組佣耐,但是這個(gè)數(shù)組是有序的政勃,比如數(shù)字是按照從小到大的順序排列的,現(xiàn)在從這個(gè)數(shù)組里面找一個(gè)數(shù)兼砖。

如何最快的找到這個(gè)數(shù)呢奸远?首先,之前有說過掖鱼,這個(gè)數(shù)組是有序的而且由小到大排列然走,那么如果第一次找到的數(shù)比要找的那個(gè)數(shù)小,就會(huì)從這個(gè)數(shù)的后面開始找戏挡,否則就從這個(gè)數(shù)的前面開始找芍瑞,這樣找到的第二個(gè)數(shù)再使用這個(gè)方法開始找,直至找到的數(shù)剛好和要找的這個(gè)數(shù)相等褐墅。

好拆檬,查找的方法了解了,怎么找才能使查找的次數(shù)最少呢妥凳?這里介紹一個(gè)我們經(jīng)尘构幔看到的或者自己玩過的一個(gè)游戲,就是報(bào)數(shù)人在某個(gè)范圍內(nèi)隨便報(bào)一個(gè)數(shù)逝钥,但是這個(gè)數(shù)字不能讓猜數(shù)人知道屑那,然后猜數(shù)人開始猜數(shù),報(bào)數(shù)人每次都需要根猜數(shù)人提供的數(shù)字和自己報(bào)的數(shù)字進(jìn)行比較,告訴猜數(shù)人他的數(shù)字是大了還是小了持际,猜數(shù)人需要在最少的回合內(nèi)猜到這個(gè)數(shù)沃琅。比如現(xiàn)在這個(gè)數(shù)是在 1 到 100 之間,那么首先肯定就會(huì)猜 50蜘欲,為什么是 50 呢益眉,因?yàn)?50 剛好是個(gè)中間數(shù),無(wú)論這個(gè)數(shù)字比要猜的數(shù)字大還是小姥份,都可以排除一半范圍的數(shù)郭脂。這樣如果猜數(shù)人說“大了”,那就從 1 到 50 的中間數(shù)再猜澈歉,依次下去展鸡。所以,二分查找也是這樣闷祥,因?yàn)閿?shù)組是有序的娱颊,先找到中間值,然后根據(jù)中間值的比較結(jié)果再找中間值凯砍,直至找到的這個(gè)數(shù)箱硕。

上面說簡(jiǎn)單查找的 大 O 表示法,也就是運(yùn)行時(shí)間可以表示為 O(n)悟衩,二分查找使用大 O 表示法又怎么表示呢剧罩?

還是剛才的例子,從 1 到 100 猜數(shù)座泳,如果挨個(gè)去猜惠昔,也就是使用簡(jiǎn)單查找的話, 最差的情況是猜 100 次挑势,但是使用二分查找的方法镇防,每次取中間數(shù)比較,每次都能排除一半潮饱,直到最后剩下一個(gè)數(shù)来氧,這樣最差的情況是猜 7 次。而這種每次排除一半的方式香拉,就是把數(shù)組的長(zhǎng)度不斷除以 2啦扬,直到最后的長(zhǎng)度小于 1 。這樣凫碌,二分查找的大 O 表示法就是 O(log n)扑毡。

從算法運(yùn)行時(shí)間可以看出,當(dāng) n 越大盛险,二分查找比簡(jiǎn)單查找要快的多瞄摊。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末勋又,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子换帜,更是在濱河造成了極大的恐慌赐写,老刑警劉巖,帶你破解...
    沈念sama閱讀 221,635評(píng)論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件膜赃,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡揉忘,警方通過查閱死者的電腦和手機(jī)跳座,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,543評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)泣矛,“玉大人疲眷,你說我怎么就攤上這事∧啵” “怎么了狂丝?”我有些...
    開封第一講書人閱讀 168,083評(píng)論 0 360
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)哗总。 經(jīng)常有香客問我几颜,道長(zhǎng),這世上最難降的妖魔是什么讯屈? 我笑而不...
    開封第一講書人閱讀 59,640評(píng)論 1 296
  • 正文 為了忘掉前任蛋哭,我火速辦了婚禮,結(jié)果婚禮上涮母,老公的妹妹穿的比我還像新娘谆趾。我一直安慰自己,他們只是感情好叛本,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,640評(píng)論 6 397
  • 文/花漫 我一把揭開白布沪蓬。 她就那樣靜靜地躺著,像睡著了一般来候。 火紅的嫁衣襯著肌膚如雪跷叉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,262評(píng)論 1 308
  • 那天吠勘,我揣著相機(jī)與錄音性芬,去河邊找鬼。 笑死剧防,一個(gè)胖子當(dāng)著我的面吹牛植锉,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播峭拘,決...
    沈念sama閱讀 40,833評(píng)論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼俊庇,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼狮暑!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起辉饱,我...
    開封第一講書人閱讀 39,736評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤搬男,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后彭沼,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體缔逛,經(jīng)...
    沈念sama閱讀 46,280評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,369評(píng)論 3 340
  • 正文 我和宋清朗相戀三年姓惑,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了褐奴。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,503評(píng)論 1 352
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡于毙,死狀恐怖敦冬,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情唯沮,我是刑警寧澤脖旱,帶...
    沈念sama閱讀 36,185評(píng)論 5 350
  • 正文 年R本政府宣布,位于F島的核電站介蛉,受9級(jí)特大地震影響萌庆,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜币旧,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,870評(píng)論 3 333
  • 文/蒙蒙 一踊兜、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧佳恬,春花似錦捏境、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,340評(píng)論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至倾剿,卻和暖如春筷频,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背前痘。 一陣腳步聲響...
    開封第一講書人閱讀 33,460評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工凛捏, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人芹缔。 一個(gè)月前我還...
    沈念sama閱讀 48,909評(píng)論 3 376
  • 正文 我出身青樓坯癣,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親最欠。 傳聞我的和親對(duì)象是個(gè)殘疾皇子示罗,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,512評(píng)論 2 359

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

  • 查找是在大量的信息中尋找一個(gè)特定的信息元素惩猫,在計(jì)算機(jī)應(yīng)用中,查找是常用的基本運(yùn)算蚜点,例如編譯程序中符號(hào)表的查找轧房。本文...
    北方蜘蛛閱讀 2,894評(píng)論 1 4
  • 獨(dú)自佇立在昏黃的路燈下 可我并不孤獨(dú) 影子隨行于身 那清秋的涼風(fēng)在身邊繚繞 獨(dú)自徘徊在山澗的幽徑上 可我并不孤獨(dú) ...
    迷荼塵埃閱讀 369評(píng)論 3 7
  • 2017年3月6日接客戶通知,產(chǎn)品出現(xiàn)質(zhì)量問題绍绘,要求速派人現(xiàn)場(chǎng)處理奶镶。 我立即展開聯(lián)系,首先了解事件詳情陪拘,據(jù)客戶采購(gòu)...
    滿滿的爸爸閱讀 1,053評(píng)論 0 0
  • 陽(yáng)光明媚的日子摄乒, 靠在飄窗邊曬曬太陽(yáng)悠反, 晚上帶著星星入夢(mèng), 還可以打造窗邊愜意的小書房馍佑, 留一方角落給閱讀和思考斋否。...
    小芋圓閱讀 192評(píng)論 0 0
  • [修習(xí)正念] 即使只是修習(xí)正念幾分鐘,都能將心拉回來(lái)拭荤。正念會(huì)將我們?nèi)找顾寄揭鸪簟⒉粩嗾賳镜挠H密感再重新拉回身邊,因?yàn)檎?..
    不要多愁善感閱讀 122評(píng)論 0 0