[[432404]]

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

該算法要求待查找的數組已排序，實現步驟如下：

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

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 

測試成功

二分查找易錯點：

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

二分查找局限性：

• 針對的對象是數組結構，因為是通過下標來隨機訪問元素
• 數組必須有序
• 數組太小不合適，直接使用順序查找即可
• 數組太長不合適，數組要求連續的內存空間，數組太長不利于存儲

時間復雜度：O(logn)

空間復雜度：O(1)

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