34. 在排序数组中查找元素的第一个和最后一个位置

二分搜索

解题思路

  1. 根据题目限制空间复杂度为 O(logn)，则需要使用 二分搜索 来完成，不可以使用 滑动窗口 ，尽管滑动窗口代码量更加简单；

  2. 两次二分法查找到 target 的左右边界，返回两次二分的结果；

复杂度

  1. 时间复杂度：O(logn)

  2. 空间复杂度：O(1)

代码实现

var searchRange = function (nums, target) {
    if (nums.length === 0) {
        return [-1, -1];
    }

    let left = searchLeftRange(nums, target);
    if (left === -1) {
        return [-1, -1];
    }

    let right = searchRightRange(nums, target);
    return [left, right];
};


function searchLeftRange(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            right = mid;
        }
    }

    // 剩余最后两个元素，需要再次判断 left 元素是否等于 target
    if (nums[left] == target) {
        return left;
    }

    return -1;
}


function searchRightRange(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = left + Math.floor((right - left + 1) / 2);
        if (nums[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    return left;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 二分搜索
    1. 1.1. 解题思路
    2. 1.2. 复杂度
    3. 1.3. 代码实现