当前位置：首页 > article >正文

leetcode34-排序数组中查找数组的第一个和最后一个位置

article 2025/1/20 0:22:34

leetcode 34
之前的博客里面有写到关于二分查找的实现方法，这次这个题目也需要使用到二分查找，关于二分查找的实现可以参考博客：二分查找

在这里插入图片描述

思路

由于题目中给出的数组是递增排序的，那么我们会优先考虑到使用二分查找法，数组中可能出现多个重复的target，我们要查找的就是第一个和最后一个的target的下标。
一开始看到这个题目，可能会考虑使用暴力解法，由于这个题目在复杂度上有限制O(logn)，那么使用暴力解法应该是不能通过的，所以需要使用二分查找。
查找第一个target和最后一个target下标，我们可以进行拆分去计算，分别计算出**左边界值和右边界值**

左边界计算

1.首先使用二分查找找到第一个与target相等的值
2.判断如果这个值的左侧一项是比当前项更小
如果更小，那么说明这一项是第一个对应的目标值，mid作为左边界值
如果左侧一项和当前项一样，那么我们缩小查找范围，设置right = mid - 1; 右指针左移，然后重新进行二分查找

右边界计算

右边界的计算同左边界的计算一样
1.找到第一个与target相等的值
2.判断这个值的右侧一项是否比当前值更大
如果更大那么说明当前项是最后一个对应的目标值，mid作为右边界值
如果右侧一项和当前项一样，那么缩小查找范围，设置left = mid + 1; 左指针右移，然后重新进行二分查找

实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    const leftBorder = getLeftBorder(nums,target);
    const rightBorder = getRightBorder(nums,target);
    return [leftBorder,rightBorder]
};
// 获取左边界
function getLeftBorder(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midNum = nums[mid];
        if (midNum === target) {
            // 边界条件考虑
            // 当mid = 0时一定是左边界，当中间值的左边一项小于中间值时，也一定是左边界
            if(mid === 0 || nums[mid-1] < midNum){
                return mid;
            }else{
                // 左边项和当前项一样，那么移动右指针缩短范围，继续二分
                right = mid - 1;
            }
        } else if (target > midNum) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1
}

// 获取右边界
function getRightBorder(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midNum = nums[mid];
        if (midNum === target) {
            // 如果右侧一项比当前项更大，那么说明是右边界
            if(mid === nums.length -1 || midNum < nums[mid+1]){
                return mid
            }else{
                left = mid + 1;
            }
        } else if (target > midNum) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1
}