【剑指offer：在排序数组中查找数字】搜索左右边界：从两边向中间、二分查找

心谭博客

发布于 2020-04-21 10:40:59

1.5K0

发布于 2020-04-21 10:40:59

文章被收录于专栏：YuanXin

题目描述：统计一个数字在排序数组中出现的次数。

这题要解决的核心问题就是：搜索数字出现的左右边界。边界的差值，就是出现次数。

解法 1: 从两边向中间

思路比较简单：

从数组左侧向右遍历，遇到目标数字 target，停止，记录下标 left
从数组右侧向左遍历，遇到目标数字 target，停止，记录下标 right
如果 right 小于 left，那么说明没出现，返回 0；否则返回 right - left + 1

代码实现：

// ac地址：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
// 原文地址：https://xxoo521.com/2020-03-13-find-num-in-sorted/
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    if (!nums.length) return 0;

    let left = 0,
        right = nums.length - 1;
    while (nums[left] !== target && left < nums.length) {
        ++left;
    }
    while (nums[right] !== target && right >= 0) {
        --right;
    }

    return left <= right ? right - left + 1 : 0;
};

时间复杂度是$O(N)$，空间复杂度是$O(1)$。

解法 2: 二分查找（巧妙）

二分查找一般用来查找数字在有序数组中是否出现过。进一步想，它可以用来不断在子序列中搜索对应数字。所以，我们就可以用它来向左边子序列中不断搜索，确认左边界；同样的思路，确认右边界。

这可能还是有点抽象，举个 ?。以数组 2、3、3、3、2 为例，我们要搜索数字 3 的左右边界。假设我们先尝试搜索左边界下标 start。

按照二分法思路，arr[mid] = arr[2] = 3，更新 start 为 2，同时缩小搜索范围到 [0, mid - 1] = [0, 1]。继续按照二分思路，搜索范围缩小到[1, 1]，发现值为 3，更新 start 为 1。结束。

按同样方法，可以获得右边界下标 end。

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
// 原文地址：https://xxoo521.com/2020-03-13-find-num-in-sorted/
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    const length = nums.length;
    let start = -1,
        end = -1;

    let left = 0,
        right = length - 1;
    // 找到左边界：找到第一次出现
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            start = mid;
            right = mid - 1; // important
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    left = 0;
    right = length - 1;
    // 找到右边界：找到第2次出现
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            end = mid;
            left = mid + 1; // important
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return start <= end && start !== -1 ? end - start + 1 : 0;
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-03-13，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度