二分查找

二分查找也称折半查找

算法要求

• 必须采用有序存储数据结构
• 必须按照关键字大小有序排列

思想

将n个元素分成大小相等的两部分，取a[n/2]与x做比较，若x = a[n/2]，则找到该元素，算法结束，如果x < a[n/2]，则证明x在左半边，故在数组的左半边查找，如果x > a[n/2]，则证明x在右半边，故在数组的右半边查找，以此类推

时间复杂度

时间复杂度为O(logn)

代码如下（JavaScript）

function binarySearch(arr, x) {
        var low = 0;
        var high = arr.length - 1;
        while (low <= high) {
            var middle = parseInt((high + low) / 2);
            if (x == arr[middle]) {
                return middle;
            }
            else if (x < arr[middle]) {
                high = middle - 1;
            }
            else {
                low = middle + 1;
            }
        }

        return -1;
    }

    var arr = [1, 2, 3, 4, 5];
    binarySearch(arr, 3); //2