No puedo entender por qué mi función excede el límite de tiempo y por qué puede entrar en un ciclo infinito. ¿Hay algún caso extremo que podría estar pasando por alto?
Aquí está la descripción del problema:
Dada una matriz ordenada de enteros distintos y un valor objetivo, devuelve el índice si se encuentra el objetivo. Si no, devuelve el índice donde estaría si se insertara en orden.
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; }; 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))Podría usar una condición que realmente detenga el bucle, por ejemplo, marcando izquierda y derecha y si la izquierda es mayor que la derecha, salga del bucle.
while (leftIndex < rightIndex) { Otra parte es bajar el índice de pivote, ya sea usando Math.floor o con >> desplazamiento a la derecha .
const pivot = (rightIndex + leftIndex) >> 1; // right shift by one bitEsto evita omitir algunos índices y produce resultados predecibles.
Para verificar todo, use una matriz con elementos pares e impares y verifique cada valor de la matriz.
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; }