在排序数组中查找数字 I

解题思路：

  1. 两次二分查找找到 target 左右边界；

  2. target 出现次数 = 右边界 - 左边界 + 1；

复杂度：

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

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

代码实现：

function search(nums: number[], target: number): number {
    let left = search_leftBond(nums, target);
    let right = search_rightBond(nums, target);
    return (left === -1 || right === -1) ? 0 : right - left + 1;
};

function search_leftBond(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = left + (right - left >> 1);
        if (nums[mid] === target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }

    // target 大于数组中的最大值，left 一直向右查找，数组下标越界
    if (left == nums.length) return -1;

    // 判断一下 nums[left] 是不是 target（target 位于中间，可能并不存在数组中）
    return nums[left] == target ? left : -1;
};

function search_rightBond(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = left + (right - left >> 1);

        if (nums[mid] === target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }

    // target 不在数组里，left 指针越界（target 小于数组中所有的元素）
    if (left - 1 < 0) return -1;

    // 判断一下 nums[left] 是不是 target（target 位于中间，可能并不存在数组中）
    // 由于等于 target 的时候，left 又加了 1，所以结果要减掉
    return nums[left - 1] == target ? (left - 1) : -1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

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

粽子

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

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

了解更多

目录

  1. 1. 在排序数组中查找数字 I
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：