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;
}

參考資料