专栏首页YuanXin【剑指offer:0~n-1中缺失的数字】二分查找的妙用

【剑指offer:0~n-1中缺失的数字】二分查找的妙用

题目描述:一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n-1 之内。在范围 0 ~ n-1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。

解法:二分查找

利用二分查找,整体流程是:

  • left 指向 0,right 指向最后一个元素
  • 计算中间坐标 mid:
    • 如果mid = nums[mid],说明[0, mid]范围内不缺失数字,left 更新为 mid + 1
    • 如果mid < nums[mid],说明[mid, right]范围内不缺失数字,right 更新为 mid - 1
  • 检查 left 是否小于等于 mid,若成立,返回第 2 步;否则,向下执行
  • 返回 left 即可

注意,根据题意,可以知道mid > nums[mid]这种情况不存在。

代码实现如下:

// ad地址:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-03-14-missing-number/
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (mid === nums[mid]) {
            left = mid + 1;
        } else if (mid < nums[mid]) {
            right = mid - 1;
        }
    }

    return left;
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    心谭博客
  • 【剑指offer:和为s的两个数字】双指针

    题目描述:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

    心谭博客
  • LeetCode 53.最大子序列和 - JavaScript

    题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    心谭博客
  • 【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值(LeetCode153题)

    文章首发于本人CSDN账号:https://blog.csdn.net/tefuirnever

    我是管小亮
  • [Leetcode][python]Sort Colors/颜色分类

    给出一个由红、白、蓝三种颜色组成的数组,把相同颜色的元素放到一起,并整体按照红、白、蓝的顺序。用0表示红色,1表示白色,2表示蓝色。这题也称为荷兰国旗问题。

    后端技术漫谈
  • 【手绘漫画】图解LeetCode之寻找旋转排序数组中的最小值 II(LeetCode154题)

    今天是第二期,争取每天一期,最多两天一期,欢迎大家监督我。。。公众号监督最好!!!

    我是管小亮
  • [Leetcode][python]寻找峰值

    https://leetcode-cn.com/problems/find-peak-element/description/

    后端技术漫谈
  • 【Leetcode】81. 搜索旋转排序数组 II

    ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    Leetcode名企之路
  • LeetCode-15-3Sum

    Given an array S of n integers, are there elements a, b, c in S such that a + b ...

    欠扁的小篮子
  • [Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

    把一个严格升序的数组进行旋转,如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标,不存在返回-1。...

    后端技术漫谈

扫码关注云+社区

领取腾讯云代金券