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

参考资料