場景

??假設(shè)有這樣一個“猜數(shù)字”的游戲：裁判在1~100之間想一個數(shù)字，我們報數(shù)字來猜裁判心中所想的數(shù)字，裁判能提示我們所猜的這個數(shù)字是“大了”，“小了”，或者“猜對啦！”，直到裁判說“猜對啦”，這個游戲才算結(jié)束！

方案一

最直接的一個辦法就是，我們可以有序的從1報到100，代碼實現(xiàn)如下：

// 用隨機(jī)數(shù)來模擬裁判心中所想的數(shù)字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的數(shù)字是${num}`)
// for循環(huán)模擬我們猜的過程
for(let i = 1; i <= 100; i++) {
    if(i < num){
        console.log('小了')
    } else if(i === num){
        console.log(`猜中啦！這個數(shù)字是${i}`)
        console.log(`一共猜了${i}次`)
        break
    }
}

猜想

以上確實是不失為一種方案，但可以看出，這種方案最少需要猜測1次，最多需要猜測100次。想一想，有沒有一種方法，能夠讓我們盡可能少的猜測就能猜到這個數(shù)字。假如我們從中間開始猜，每次都能排除掉一半的數(shù)字，然后繼續(xù)在剩下的數(shù)字中取中間值，這樣又能排除掉一半......重復(fù)這個動作，直到找到正確的數(shù)字，這便是二分查找算法了。并且我們還有一個“大了”的條件我們還沒有用上，如果用這種方式，那么這個條件就能用上了。

方案二

每次我們從最中間的數(shù)開始猜，如果有小數(shù)點（1~100最中間的數(shù)是50.5）就進(jìn)行向下取整。

// 還是用隨機(jī)數(shù)來模擬裁判心中所想的數(shù)字（1~100）
let num = Math.floor(Math.random() * 100 + 1)
console.log(`裁判心中想的數(shù)字是${num}`)
// 定義（0~100）這個區(qū)間的小值lit，最大值big，和中間值mid，i用來記錄循環(huán)的次數(shù)
let lit = 0, big = 100, mid = Math.floor((lit + big) / 2), i = 0
// 只要范圍沒有縮小到只剩一個元素，就循環(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(`猜對啦！這個數(shù)字是${mid}`)
        console.log(`一共猜了${i}次`)
        break
    }
}

結(jié)論

方案一，最多需要猜測100次，而方案二最多只需要7次，可見二分查找的效率比普通循環(huán)的要高很多。一般對于包含了n個元素的有序列表來說，二分查找最多只需要次就能找到。