二分查找法

二分查找法(binary search algorithm)，也称折半搜索算法(half-interval search algorithm)、对数搜索算法(logarithmic search algorithm)，是一种在有序数组中查找某一特定元素的搜索方法。

原理：每次跟区间中间元素对比，将待查找区域缩小一半，直到找到元素或区间缩小为0。

算式

给出长度为n的有序数组A及目标值T。

• 令L为0，R为n - 1；
• 如果L > R，则查找失败结束；
• 令m(中间值元素)为|(L + R) / 2|；(防止算术溢出，一半采用|L + (R - L) / 2|代替)
• 如果Am < T，令L为m + 1并回到步骤二；
• 如果Am > T，令R为m - 1并回到步骤二；
• 当Am = T，查找结束，回传值m。

这个迭代步骤会持续透过两个变量追踪搜索的边界。

代码实现

循环

function binarySearch(arr, value) {
    if (!Array.isArray(arr)) {
        return -1;
    }

    const length = arr.length;
    let left = 0;
    let right = length - 1;

    if (value < arr[left] || value > arr[right]) {
        return -1;
    }

    while(left <= right) {
        const mid = ~~((left + right) / 2);
        if (arr[mid] === value) {
            return mid;
        }
        if (arr[mid] > value) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

递归

function binarySearch(arr, value, left, right) {
    if (!Array.isArray(arr)) {
        return -1;
    }
    
    if (!arr.length) {
        return -1;
    }
    
    if (left > right) {
        return -1;
    }

    if (value < arr[left] || value > arr[right]) {
        return -1;
    }

    const mid = ~~((left + right) / 2);
    if (arr[mid] === value) {
        return mid;
    }

    if (arr[mid] > value) {
        return binarySearch(arr, value, left, mid - 1);
    } else {
        return binarySearch(arr, value, mid + 1, right);
    }
}