34. Find First and Last Position of Element in Sorted Array

Leetcode 問題: 34. Find First and Last Position of Element in Sorted Array
Categories:
Tags:

題目

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

傳入一個 非遞減（non-decreasing）排序的數字陣列 nums，所以陣列中的數字可能相等或大於的狀況慢慢增加上去

傳入一個要尋找的目標數字 target，找出這個目標數字在 數字陣列 nums 中的 第 1 個出現的索引位置 及 最後 1 個出現的索引位置，回傳成陣列 [第 1 個出現的索引位置, 最後 1 個出現的索引位置]

e.g. [5,7,7,8,8,10]

要尋找的 目標數字 target 是 8，所以回傳的目標數字出現位置索引 則為 [3, 4]

如果要尋找的目標數字 target 是 6，但 6 不存在這個 數字陣列 nums 中，則回傳 [-1, -1]

Example

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Input: nums = [], target = 0
Output: [-1,-1]

演算法

1. 分別找 左邊界（第 1 個出現） 及 右邊界（最後 1 個出現） 的數字

可以指定數字並找到該數字，但我們分別需要 左邊界（第 1 個出現） 及 右邊界（最後 1 個出現） 的數字

所以需要透過 binarySearch 分別找 2 次，一次找左邊，一次找右邊

2. 二分法切割要檢查的數字索引範圍

設定左右指標，匡選檢查的範圍

  • 左邊指標: 0，數字陣列最左方索引
  • 右邊指標: 數字陣列最右方索引，全部的版本號數字

取左右指標索引，左右逼近到可能出現的最接近的數字，如果「左邊數字索引」與「右邊數字索引」沒有相交，表示還可以再尋找

將數字索引位置切割成一半，拿左右字母索引的平均數當作切割點，可以把數字切割成一半，減少要檢查的範圍

3.「中間指標數字」與「右指標數字」比較

狀況 A. 當「中間指標數字」小於「目標數字」

表示「左邊」的數字序列都是「小於目標數字」不需要再找，要往「右邊」尋找

將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查

狀況 B. 當「中間指標數字」大於「目標數字」

表示「右邊」的數字序列都是「大於目標數字」不需要再找，要往「左邊」尋找

將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查

狀況 C. 當「中間指標數字」等於「目標數字」

找到了！將「目前中間指標數字」設定到「目標數字索引位置」

但因為數字可能會「連續出現」，所以要判斷要找「最左邊」的數字還是「最右邊」的數字

狀況 C1. 要找「最左邊」的數字

就要往目前數字「左邊」找看看還有沒有同樣的數字

將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查

狀況 C2. 要找「最右邊」的數字

就要往目前數字「右邊」找看看還有沒有同樣的數字

將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查

4. 回傳找到的數字指標

最後會找到不能再找時，回傳此目標索引，若沒有找到的話，預設會回傳 -1

答案

JavaScript

function searchRange(numsList, targetNumber) {
    // 先找出現數字的左邊索引
    var leftNumberIndex = binarySearch(numsList, targetNumber, true);
    // 設定右邊索引與左邊索引相同
    var rightNumberIndex = leftNumberIndex;
    if (rightNumberIndex !== -1) {
        // 如果原本左邊就沒有找到，那右邊就不用找了
        // 如果有找到左邊索引的數字，那就接著找右邊索引數字
        rightNumberIndex = binarySearch(numsList, targetNumber, false);
    }
    return [leftNumberIndex, rightNumberIndex];
}

function binarySearch(numsList, targetNumber, isFindLeftBias) {
    // 左指標
    var leftPointer = 0;
    // 右指標
    var rightPointer = numsList.length - 1;
    // 目標數字索引位置，預設為 -1 沒有找到該數字
    var targetNumberIndex = -1;
    while (leftPointer <= rightPointer) {
        // 當「左指標」還沒超過「右指標」，表示還沒比完，可以繼續比較
        // 將檢查的指標切半，用「中間指標」當作參考指標
        var middlePointer = Math.floor((rightPointer + leftPointer) / 2);
        // 「中間指標」的數字
        var middleNumber = numsList[middlePointer];
        if (middleNumber < targetNumber) {
            // 當「中間指標數字」小於「目標數字」
            // 表示「左邊」的數字序列都是「小於目標數字」不需要再找，要往「右邊」尋找
            // 將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查
            leftPointer = middlePointer + 1;
        }
        else if (middleNumber > targetNumber) {
            // 當「中間指標數字」大於「目標數字」
            // 表示「右邊」的數字序列都是「大於目標數字」不需要再找，要往「左邊」尋找
            // 將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查
            rightPointer = middlePointer - 1;
        }
        else {
            // 當「中間指標數字」等於「目標數字」
            // 將「目前中間指標數字」設定到「目標數字索引位置」
            targetNumberIndex = middlePointer;
            // 但因為數字可能會「連續出現」，所以要判斷要找「最左邊」的數字還是「最右邊」的數字
            if (isFindLeftBias) {
                // 當傳入要找「最左邊」的數字，就要往目前數字「左邊」找看看還有沒有同樣的數字
                // 將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查
                rightPointer = middlePointer - 1;
            }
            else {
                // 當傳入要找「最右邊」的數字，就要往目前數字「右邊」找看看還有沒有同樣的數字
                // 將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查
                leftPointer = middlePointer + 1;
            }
        }
    }
    // 最後會找到此目標索引
    return targetNumberIndex;
}

TypeScript

function searchRange(numsList: number[], targetNumber: number): number[] {
    // 先找出現數字的左邊索引
    let leftNumberIndex = binarySearch(numsList, targetNumber, true);
    // 設定右邊索引與左邊索引相同
    let rightNumberIndex: number = leftNumberIndex;
    if (rightNumberIndex !== -1) {
        // 如果原本左邊就沒有找到，那右邊就不用找了
        // 如果有找到左邊索引的數字，那就接著找右邊索引數字
        rightNumberIndex = binarySearch(numsList, targetNumber, false);
    }

    return [leftNumberIndex, rightNumberIndex];
};

function binarySearch(numsList: number[], targetNumber: number, isFindLeftBias: boolean): number {
    // 左指標
    let leftPointer: number = 0;
    // 右指標
    let rightPointer: number = numsList.length - 1;
    // 目標數字索引位置，預設為 -1 沒有找到該數字
    let targetNumberIndex: number = -1;

    while (leftPointer <= rightPointer) {
        // 當「左指標」還沒超過「右指標」，表示還沒比完，可以繼續比較
        // 將檢查的指標切半，用「中間指標」當作參考指標
        let middlePointer = Math.floor((rightPointer + leftPointer) / 2);

        // 「中間指標」的數字
        let middleNumber: number = numsList[middlePointer];

        if (middleNumber < targetNumber) {
            // 當「中間指標數字」小於「目標數字」
            // 表示「左邊」的數字序列都是「小於目標數字」不需要再找，要往「右邊」尋找
            // 將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查
            leftPointer = middlePointer + 1;
        } else if (middleNumber > targetNumber) {
            // 當「中間指標數字」大於「目標數字」
            // 表示「右邊」的數字序列都是「大於目標數字」不需要再找，要往「左邊」尋找
            // 將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查
            rightPointer = middlePointer - 1;
        } else {
            // 當「中間指標數字」等於「目標數字」
            // 將「目前中間指標數字」設定到「目標數字索引位置」
            targetNumberIndex = middlePointer;
            // 但因為數字可能會「連續出現」，所以要判斷要找「最左邊」的數字還是「最右邊」的數字
            if (isFindLeftBias) {
                // 當傳入要找「最左邊」的數字，就要往目前數字「左邊」找看看還有沒有同樣的數字
                // 將「右指標」設定為目前的「中間指標 - 1」，再繼續檢查
                rightPointer = middlePointer - 1
            } else {
                // 當傳入要找「最右邊」的數字，就要往目前數字「右邊」找看看還有沒有同樣的數字
                // 將「左指標」設定為目前的「中間指標 + 1」，再繼續檢查
                leftPointer = middlePointer + 1;
            }
        }
    }

    // 最後會找到此目標索引
    return targetNumberIndex;
}

參考資料