如何避免潜在的无限循环？

Question

我不明白为什么我的函数会超过时间限制，为什么会进入无限循环。有没有我可能忽略的极端情况？

问题描述如下：

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

var searchInsert = function(nums, target) {
  if (target > nums[nums.length - 1]) { // If target is greater 
    return nums.length;                 // than the largest element
  };
  let leftIndex = 0;                   // implementing binary search
  let rightIndex = nums.length - 1;
  while (leftIndex != rightIndex) {
    let pivot = Math.round((rightIndex + leftIndex) / 2);
    if (target == nums[pivot]) {
      return pivot;
    } else if (target < nums[pivot]){
        rightIndex = pivot - 1; 
    } else {
        leftIndex = pivot + 1;
    }
  };
  return target <= nums[leftIndex] ? leftIndex : leftIndex + 1;
};

Answer 1

const array = [1, 2, 6, 8, 10, 16, 18, 20, 33, 55]

function findTarget(target){
  if(array.includes(target)){
    return "Target was found at index : " + array.indexOf(target)
  }
  if(array[0] > target)
    return "Target should be inserted at index : " + 0
  for(let i = 0; i < array.length; i+=1){
    if(array[i] < target && array[i + 1] > target){
      return "Target should be inserted at index : " + (i+1)
    }
  }
  return "Target should be inserted at index : " + array.length
}

console.log(findTarget(8))
console.log(findTarget(9))
console.log(findTarget(60))
console.log(findTarget(0))

Answer 2

您可以使用真正停止循环的条件，例如检查左右，如果左边大于右边则退出循环。

while (leftIndex < rightIndex) {

另一部分是通过使用 Math.floor or by >> right shift.

来降低枢轴索引

const pivot = (rightIndex + leftIndex) >> 1; // right shift by one bit

这可以防止遗漏一些索引并产生可预测的结果。

要检查全部，请使用包含偶数项和奇数项的数组并检查数组的每个值。

var searchInsert = function(nums, target) {
    let leftIndex = 0;
    let rightIndex = nums.length - 1;

    if (target > nums[rightIndex]) return nums.length;                 

    while (leftIndex < rightIndex) {
        const pivot = (rightIndex + leftIndex) >> 1;

        if (target === nums[pivot]) return pivot;

        if (target < nums[pivot]) rightIndex = pivot - 1; 
        else leftIndex = pivot + 1;
    };
    return target <= nums[leftIndex] ? leftIndex : leftIndex + 1;
};

console.log(searchInsert([0, 1, 2, 3, 4, 5], -0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 0));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 1));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 1.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 2));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 2.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 3));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 3.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 4));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 4.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 5));
console.log(searchInsert([0, 1, 2, 3, 4, 5], 5.5));
console.log('--');
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], -0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 0));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 0.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 1));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 1.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 2));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 2.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 3));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 3.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 4));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 4.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 5.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 6));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 6.5));
console.log(searchInsert([0, 1, 2, 3, 4, 5, 6], 7));

.as-console-wrapper { max-height: 100% !important; top: 0; }

如何避免潜在的无限循环？

How do I avoid a potential infinite loop?

javascript

infinite-loop

while-loop