Escribí este código, pero no entiendo por qué funciona de esta manera, especialmente usando los ejemplos tercero y cuarto como entrada. ¿Por qué la posición 'media' se queda tan atrás? -en el número 5 (o índice 2) usando la matriz [1, 3, 5, 6] y el número 7 como objetivo?
y como mejorarlo?? No puedo pensar en una forma más corta o mejor de verificar if/elses cuando el valor objetivo no está en la matriz, especialmente si la entrada es una matriz con solo un valor y el objetivo a encontrar es 0. Tal vez una mejor manera de verificar los diferentes escenarios posibles. O cómo verificar mejor el lugar correcto del objetivo sin tantos if/elses.
Por ejemplo, ¿este código es lo suficientemente bueno para una entrevista de codificación? ¿Qué puedo hacer mejor?
de LeetCode:
Posición de inserción de búsqueda
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.
Debe escribir un algoritmo con una complejidad de tiempo de ejecución O(log n).
Ejemplo 1: Entrada: nums = [1,3,5,6], objetivo = 5 Salida: 2
Ejemplo 2: Entrada: nums = [1,3,5,6], objetivo = 2 Salida: 1
Ejemplo 3: Entrada: nums = [1,3,5,6], objetivo = 7 Salida: 4
Y especialmente este: Ejemplo 4: Entrada: nums=[1], target= 0
Restricciones: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums contiene valores distintos ordenados en orden ascendente. -104 <= objetivo <= 104
este es mi código:
/** * @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; } } }; El problema radica en la variable que está buscando después del ciclo while .
En un algoritmo de búsqueda binaria "clásico", ir más allá del bucle while indicaría que la needle no está presente en el haystack . Sin embargo, en el caso de este problema, simplemente necesitamos devolver right + 1 en este lugar en el código (en lugar de marcar el middle ).
Su código ajustado para esto:
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) );Además, lo siguiente es redundante ...
middle = nums.length>1 ? (Math.floor(left + (right - left)/2)) : 0;... y se puede acortar a:
middle = Math.floor((left + right) / 2); const searchInsertProblem = (arr, n) => { let start = 0; let end = arr.length - 1; while (start <= end) { const middle = Math.floor((start + end) / 2); if (arr[middle] === n) { return middle; } // on target if (arr[middle] > n) { end = middle - 1; } // overshoot else { start = middle + 1; } // undershoot } return end + 1; }; console.log( searchInsertProblem([1,3,5,6], 5), searchInsertProblem([1,3,5,6], 2), searchInsertProblem([1,3,5,6], 7), searchInsertProblem([1], 0) );