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