简述二分查找算法与时间复杂度，并实现一个二分查找算法

二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写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/