什么是簡(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)單查找要快的多瞄摊。