如何使检查更坚固和更短？

Question

我写了这段代码，但我不知道为什么会这样，尤其是使用第三和第四个示例作为输入。为什么“中间”地位仍然如此落后-在数字5（或索引2）中使用[1，3，5，6]数组和数字7作为目标？？

如何让它变得更好？？当目标值不在数组中时，我想不出一种更短或更好的方法来检查if/elses，尤其是当输入是一个只有一个值的数组并且要查找的目标为0时。也许是检查可能的不同场景的更好方法。或者如何在没有那么多if/els的情况下更好地检查目标的正确位置。

例如，这段代码对于编码面试来说够好了吗？我能做得更好吗？

来自LeetCode:

搜索插入位置

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

您必须编写一个运行时复杂度为O（log n）的算法。

示例1：输入：nums=[1,3,5,6]，目标=5输出：2

示例2：输入：nums=[1,3,5,6]，目标=2输出：1

示例3：输入：nums=[1,3,5,6]，目标=7输出：4

尤其是这个：示例4：输入：nums=[1]，target=0

约束：1

这是我的代码:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length -1;
    let middle;
    while(left <= right){
        middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;
        if(nums[middle] === target){
            return middle;
        } else if(target < nums[middle]){
            right = middle -1;
        } else {
            left = middle + 1;
        }
    }
    
    console.log(`Middle: ${middle}`);
    console.log(`Middle-1: ${nums[middle-1]}`);
    if(nums.lenght === 1){
        return 0;
    } else {
        if((target < nums[middle] && target > nums[middle-1] )|| (target < nums[middle] && nums[middle-1] === undefined)){ /*
No more items to the left ! */
        return middle; 
    } else if(target<nums[middle] && target<nums[middle-1]){
        return middle-1;
    } else if(target > nums[middle] && target > nums[middle + 1]) {
        return middle + 2; /* Why the 'middle' is so behind here? using the THIRD example as input?? */
    } else {
        return middle + 1;
    }
    }
};

Answer 1

问题在于您在 while 循环后检查的变量。

在“经典”二叉搜索算法中，超出while循环将表明大海捞针中不存在。但是，如果出现此问题，我们只需要在代码的这个地方返回右 1（而不是检查中间）。

您的代码为此进行了调整：

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length -1;
    let middle;
    while(left <= right){
        middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;
        if(nums[middle] === target){
            return middle;
        } else if(target < nums[middle]){
            right = middle -1;
        } else {
            left = middle + 1;
        }
    }
    
    return right + 1;
};

console.log(
  searchInsert([1,3,5,6], 5),
  searchInsert([1,3,5,6], 2),
  searchInsert([1,3,5,6], 7),
  searchInsert([1], 0)
);