[[432404]]

二分查找也稱折半查找算法，它是一種簡單易懂的快速查找算法。例如我隨機(jī)寫0-100之間的一個數(shù)字，讓你猜我寫的是什么?你每猜一次，我就會告訴你猜的大了還是小了，直到猜中為止。

該算法要求待查找的數(shù)組已排序，實現(xiàn)步驟如下：

• 選擇數(shù)組中的中間數(shù)
• 查找數(shù)與中間數(shù)對比，比中間數(shù)低，則去中間數(shù)左邊的子數(shù)組中尋找;比中間數(shù)高，則去中間數(shù)右邊的子數(shù)組中尋找;相等則返回查找成功
• 重復(fù)上一步，知道查找成功或失敗

function binarySearch(items, item) { 
    var low = 0, 
        high = items.length - 1, 
        mid, elem 
    while(low <= high) { 
        mid = Math.floor((low+high)/2) 
        elem = items[mid] 
        if(elem < item) { 
            low = mid + 1 
        } else if(elem > item) { 
            high = mid - 1 
        } else { 
            return mid 
        } 
    } 
    return -1 
} 
 
// 測試 
var arr = [2,3,1,4] 
// 快排 
quickSort(arr) 
 
binarySearch(arr, 3) 
// 2 
 
binarySearch(arr, 5) 
// -1 

測試成功

二分查找易錯點(diǎn)：

• 循環(huán)退出條件是low <= high ，注意是 <=
• mid 的取值是 Math.floor((low+high)/2)
• low high 每次更新的時候，low = mid + 1 high = mid - 1

二分查找局限性：

• 針對的對象是數(shù)組結(jié)構(gòu)，因為是通過下標(biāo)來隨機(jī)訪問元素
• 數(shù)組必須有序
• 數(shù)組太小不合適，直接使用順序查找即可
• 數(shù)組太長不合適，數(shù)組要求連續(xù)的內(nèi)存空間，數(shù)組太長不利于存儲

時間復(fù)雜度：O(logn)

空間復(fù)雜度：O(1)

leetcode：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-user7746o/