二分查找

基本概念

二分查找（Binary Search）算法，也叫折半查找算法。

二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

算法复杂度O(logn)。

使用场景

在有序的数列中寻找某个数。

例如：我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。你来想想，如何快速猜中我写的数字呢？

假设我写的数字是 23，猜数过程如下。

二分查找的框架

function binarySearch(nums, target) {
    var left = 0; 
    var right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        var mid = Math.floor((right + left) / 2);
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}