搜索插入位置-错误答案

Question

我正在解决一个问题（leetcode 35）。我的代码在运行代码结果中被接受，但是当我提交它时 return 错误 answer.I 不太明白我的回答有什么问题。

给定一个排序数组和一个目标值，return如果找到目标则为索引。如果不是，return 如果按顺序插入它的索引。

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

下面是我的code.Please帮我提前知道bug在哪里is.Thanks

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
 var min = 0;
 var max = nums.length - 1;
    var guess;
    
    while(min <= max) {
    guess = Math.floor((max + min) / 2);
        if (nums[guess] === target) {
        return guess;
    }
    else if (nums[guess] < target) {
        min = guess + 1;
    }
    else {
        max = guess - 1;
    }
    }
};

提交详情


Input: [1,3,5,6]
2
Output: undefined
Expected: 1

Answer 1

是因为你漏掉了没有找到目标号码的情况。在这些情况下，您需要 return 目标数字可以插入输入数组的索引，同时数组保持排序。

这是您 JS 代码的正确版本：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
 var min = 0;
 var max = nums.length - 1;
    let guess = 0
    
    while(min <= max) {
    const mid = Math.floor((max + min) / 2);
        if (nums[mid] === target) {
        return mid;
    }
    else if (nums[mid] < target) {
        min = mid + 1;
        guess = mid+1
    }
    else {
        max = mid - 1
        guess = mid;
    }
    }
    return guess
};

您最初将 guess 设置为 0。当你二分搜索时，如果你找到 target，只是 return mid 这是当前最小值和最大值之间的中点。

但是如果 nums[mid] 小于 target 你可以确定 target 至少需要插入到 mid+1 因为 nums[mid] 需要在 target 的左侧，以便数组保持排序。

另一方面，如果 nums[mid] > target，target 必须将 nums[mid] 及其右侧的所有内容推向右侧，并占据 nums[mid] 处元素的索引.所以，在这种情况下，我们设置 guess = mid.

最后我们return guess。那是因为我们在数组中没有目标。

这是一个可以说更优雅但更难阅读的解决方案：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
 let left = 0;
 let right = nums.length

    
    while(left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
        left = mid + 1;
    }
    else {
        right = mid
        guess = mid;
    }
    }
    return left
};

如果您已经理解前面的解决方案，请仔细阅读并尝试理解它是如何工作的。

另请注意，为避免溢出，您需要使用 left + IntergerDivide(right - left).

计算 mid

搜索插入位置-错误答案

Search Insert Position-Wrong answe

javascript

algorithm

binary-search