場(chǎng)景
??假設(shè)有這樣一個(gè)“猜數(shù)字”的游戲：裁判在1~100之間想一個(gè)數(shù)字竿音，我們報(bào)數(shù)字來(lái)猜裁判心中所想的數(shù)字冯键，裁判能提示我們所猜的這個(gè)數(shù)字是“大了”菲语，“小了”妄辩，或者“猜對(duì)啦！”山上，直到裁判說(shuō)“猜對(duì)啦”眼耀，這個(gè)游戲才算結(jié)束！
方案一
最直接的一個(gè)辦法就是佩憾，我們可以有序的從1報(bào)到100哮伟，代碼實(shí)現(xiàn)如下：
// 用隨機(jī)數(shù)來(lái)模擬裁判心中所想的數(shù)字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的數(shù)字是${num}`)
// for循環(huán)模擬我們猜的過(guò)程
for(let i = 1; i <= 100; i++) {
if(i < num){
console.log('小了')
} else if(i === num){
console.log(`猜中啦！這個(gè)數(shù)字是${i}`)
console.log(`一共猜了${i}次`)
break
}
}
猜想
以上確實(shí)是不失為一種方案妄帘，但可以看出楞黄，這種方案最少需要猜測(cè)1次，最多需要猜測(cè)100次抡驼。想一想鬼廓，有沒(méi)有一種方法，能夠讓我們盡可能少的猜測(cè)就能猜到這個(gè)數(shù)字致盟。假如我們從中間開(kāi)始猜捞稿，每次都能排除掉一半的數(shù)字彪标，然后繼續(xù)在剩下的數(shù)字中取中間值，這樣又能排除掉一半......重復(fù)這個(gè)動(dòng)作，直到找到正確的數(shù)字废酷，這便是二分查找算法了蚤吹。并且我們還有一個(gè)“大了”的條件我們還沒(méi)有用上舆瘪，如果用這種方式臊岸，那么這個(gè)條件就能用上了。
方案二
每次我們從最中間的數(shù)開(kāi)始猜，如果有小數(shù)點(diǎn)（1~100最中間的數(shù)是50.5）就進(jìn)行向下取整虐杯。
// 還是用隨機(jī)數(shù)來(lái)模擬裁判心中所想的數(shù)字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的數(shù)字是${num}`)
// 定義（0~100）這個(gè)區(qū)間的小值lit玛歌，最大值big，和中間值mid擎椰，i用來(lái)記錄循環(huán)的次數(shù)
let lit = 0, big = 100, mid = Math.floor((lit + big) / 2), i = 0
// 只要范圍沒(méi)有縮小到只剩一個(gè)元素支子，就循環(huán)
while(lit <= big) {
i++
mid = Math.floor((lit + big) / 2)
// 如果中間值比num小，則把mid+1賦給lit
if(mid < num) {
console.log('小了')
lit = mid + 1
} else if(mid > num) { // 如果中間值比num大达舒，則把mid-1賦給big
console.log('大了')
big = mid - 1
} else { // 如果相等值朋，則打印mid和循環(huán)次數(shù)，并跳出循環(huán)
console.log(`猜對(duì)啦巩搏！這個(gè)數(shù)字是${mid}`)
console.log(`一共猜了${i}次`)
break
}
}
結(jié)論
方案一昨登，最多需要猜測(cè)100次，而方案二最多只需要7次贯底，可見(jiàn)二分查找的效率比普通循環(huán)的要高很多丰辣。一般對(duì)于包含了n個(gè)元素的有序列表來(lái)說(shuō)，二分查找最多只需要次就能找到禽捆。
