Binary Search 二元搜寻找到重複的值

Binary Search 二元搜寻找到重複的值
Categories:
Tags:

说明

如果 array 裡面有重複值，要寻找的 target 就可能有多个答案

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 指标 指标 指标 指标

因为可能会有多个重複的答案，所以不要一找到数字就直接回传，不然可能会回传中间的答案位置，所以必须要 等于 = 回传答案的判断式拿掉

找 最左边 的答案位置 >= target

在 array 中，找到 >= target 的元素裡面，最小的那个的 index

要找的数字是 3

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 左指标 右指标

当找到 nums[mid] == target 的时候，由于我们还不确定是否为最左，于是我们继续把 right 的位置减小，让 right = mid - 1

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 左指标 == 右指标

最后因为 左指标 与 右指标 交叉，所以回传 左指标 为最左边数字索引

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 右指标 左指标

若是 中间指标数字 小于 要找的数字 的状况

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 左指标 == 右指标

于是我们继续把 left 的位置增大，让 left = mid + 1，还是会因为 左指标 与 右指标 交叉，所以回传 左指标 为最左边数字索引

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 右指标 左指标

JavaScript

function BinarySearch(searchNumberArray, searchNumber) {
    // 左侧指标
    var leftNumberPointer = 0;
    // 右侧指标
    var rightNumberPointer = searchNumberArray.length - 1;
    while (leftNumberPointer <= rightNumberPointer) {
        // 中间指标
        var middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
        // 中间指标数字
        var middleNumber = searchNumberArray[middleNumberPointer];

        if (middleNumber >= searchNumber) {
            // 如果「中间指标数字」大于等于「要找的数字」
            // 表示「中间指标」右边的所有数字都"大于"「要找的数字」
            // 所以将「右侧指标」移动到目前「中间指标 - 1」的位置
            rightNumberPointer = middleNumberPointer - 1;
        } else if (middleNumber < searchNumber) {
            // 如果「中间指标数字」小于「要找的数字」
            // 表示「中间指标」左边的所有数字都"小于"「要找的数字」
            // 所以将「左侧指标」移动到目前「中间指标 + 1」的位置
            leftNumberPointer = middleNumberPointer + 1;
        }
    }

    // 如果都没有找到，回传最接近的指标
    return leftNumberPointer;
}

TypeScript

function BinarySearch(searchNumberArray: number[], searchNumber: number){
    // 左侧指标
    let leftNumberPointer: number = 0;
    // 右侧指标
    let rightNumberPointer: number = searchNumberArray.length - 1;

    while (leftNumberPointer <= rightNumberPointer) {
        // 中间指标
        let middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
        // 中间指标数字
        let middleNumber = searchNumberArray[middleNumberPointer];

        if (middleNumber >= searchNumber) {
            // 如果「中间指标数字」大于等于「要找的数字」
            // 表示「中间指标」右边的所有数字都"大于"「要找的数字」
            // 所以将「右侧指标」移动到目前「中间指标 - 1」的位置
            rightNumberPointer = middleNumberPointer - 1;
        } else if (middleNumber < searchNumber) {
            // 如果「中间指标数字」小于「要找的数字」
            // 表示「中间指标」左边的所有数字都"小于"「要找的数字」
            // 所以将「左侧指标」移动到目前「中间指标 + 1」的位置
            leftNumberPointer = middleNumberPointer + 1;
        }
    }

    // 如果都没有找到，回传最接近的指标
    return leftNumberPointer;
}

找 最右边 的答案位置 > target

在 array 中，找到 > target 的元素裡面，最大的那个的 index 右边的索引

要找的数字是 3

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 左指标 右指标

当找到 nums[mid] == target 的时候，由于我们还不确定是否为最右，于是我们继续把 left 的位置增加，让 left = mid + 1

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 左指标 == 右指标

最后因为 左指标 与 右指标 交叉，所以回传 左指标 为 最右边数字索引 + 1 的位置，将 左指标 - 1 就可以拿到最右边的答案索引值

索引 0 1 2 3 4 5 6 7 8 9
数字阵列 0 1 2 3 3 3 3 7 8 9
指标位置 右指标 左指标

JavaScript

function BinarySearch(searchNumberArray, searchNumber) {
    // 左侧指标
    var leftNumberPointer = 0;
    // 右侧指标
    var rightNumberPointer = searchNumberArray.length - 1;
    while (leftNumberPointer <= rightNumberPointer) {
        // 中间指标
        var middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
        // 中间指标数字
        var middleNumber = searchNumberArray[middleNumberPointer];

        if (middleNumber > searchNumber) {
            // 如果「中间指标数字」大于等于「要找的数字」
            // 表示「中间指标」右边的所有数字都"大于"「要找的数字」
            // 所以将「右侧指标」移动到目前「中间指标 - 1」的位置
            rightNumberPointer = middleNumberPointer - 1;
        } else if (middleNumber <= searchNumber) {
            // 如果「中间指标数字」小于等于「要找的数字」
            // 表示「中间指标」左边的所有数字都"小于"「要找的数字」
            // 所以将「左侧指标」移动到目前「中间指标 + 1」的位置
            leftNumberPointer = middleNumberPointer + 1;
        }
    }

    // 如果都没有找到，回传最接近的指标
    return leftNumberPointer;
}

TypeScript

function BinarySearch(searchNumberArray: number[], searchNumber: number){
    // 左侧指标
    let leftNumberPointer: number = 0;
    // 右侧指标
    let rightNumberPointer: number = searchNumberArray.length - 1;

    while (leftNumberPointer <= rightNumberPointer) {
        // 中间指标
        let middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
        // 中间指标数字
        let middleNumber = searchNumberArray[middleNumberPointer];

        if (middleNumber > searchNumber) {
            // 如果「中间指标数字」大于「要找的数字」
            // 表示「中间指标」右边的所有数字都"大于"「要找的数字」
            // 所以将「右侧指标」移动到目前「中间指标 - 1」的位置
            rightNumberPointer = middleNumberPointer - 1;
        } else if (middleNumber <= searchNumber) {
            // 如果「中间指标数字」小于等于「要找的数字」
            // 表示「中间指标」左边的所有数字都"小于"「要找的数字」
            // 所以将「左侧指标」移动到目前「中间指标 + 1」的位置
            leftNumberPointer = middleNumberPointer + 1;
        }
    }

    // 如果都没有找到，回传最接近的指标
    return leftNumberPointer;
}

参考资料