如何避免潛在的無限回圈？

我無法理解為什么我的函式超過時間限制以及為什么它會進入無限回圈。是否有我可能忽略的邊緣情況？

以下是問題描述：

給定一個由不同整陣列成的排序陣列和一個目標值，如果找到目標，則回傳索引。如果不是，則回傳按順序插入的索引。

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;
};

uj5u.com熱心網友回復：

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))

uj5u.com熱心網友回復：

您可以使用真正停止回圈的條件，例如通過檢查左右以及如果左邊大于右邊退出回圈。

while (leftIndex < rightIndex) {

另一部分是通過使用Math.floor或>>右移來降低樞軸索引。

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; }

標籤：

上一篇：替換作為方法引數接收的陣列中的值

下一篇：在回圈中宣告的函式包含對變數ESLint的不安全參考