El problema real es bastante simple, implemente un algoritmo que devuelva verdadero si el valor objetivo está contenido dentro de la matriz . Aquí están las dos soluciones que se me ocurrieron. No estoy seguro de cuál sería preferible? Creo que la solución 1 es más rápida ya que no necesitamos construir una nueva matriz, sin embargo, ¿sería esto significativamente más rápido?

Solución 1:

 var searchMatrix = function(matrix, target) { let cols = matrix[0].length; let rows = matrix.length; let left = 0; let right = cols*rows - 1; while(left <= right) { let midIndex = left + Math.floor((right-left)/2); let midValue = matrix[Math.floor(midIndex/cols)][Math.floor(midIndex%cols)]; console.log(midValue); if(midValue === target) { return true; } else if(midValue < target) { left = midIndex + 1; } else { right = midIndex - 1; } } return false; };

Solución 2:

 var searchMatrix = function(matrix, target) { let arr = [] for(let row of matrix) { arr = [...arr,...row]; } let left = 0; let right = arr.length - 1; while(left <= right) { let middle = left + Math.floor((right-left)/2); if(arr[middle] === target) { return true; } else if(arr[middle] < target) { left = middle + 1; } else { right = middle - 1; } } return false; };

Según tengo entendido, el paso principal que estamos agregando es convertir la matriz en un Array regular. ¿Haría esto que el algoritmo sea O(n) ya que tenemos que agregar cada elemento a la nueva matriz?

Para la solución 1, no tenemos que crear una nueva matriz para tener un espacio constante, ¿correcto? No estoy particularmente seguro de cómo explicar que la primera solución es preferible en términos de tiempo/espacio.