【剑指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;
};

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×