Se le da una matriz de números MxN, con la propiedad de que los números aumentan a medida que avanza por cada columna y hacia la derecha en cada fila. ¿Cómo puede verificar eficientemente si un número dado está en la matriz?

Si usa cascada fraccional ( http://en.wikipedia.org/wiki/Fra …), puede resolver este problema en el tiempo [matemático] O (M + \ log N) [/ matemático] – estrictamente mejor que el propuesto [matemáticas] O (M + N) [/ matemáticas] límite propuesto anteriormente. Tenga en cuenta que este enfoque también se generaliza incluso si atenuamos las restricciones en la cuadrícula, de modo que solo se clasifica una dimensión y la otra no.

Hay muchos enfoques para resolver este problema, veamos algunos de ellos.

Enfoque 1:
Verifique el número uno por uno mirando cada elemento de la matriz.
Este enfoque no es eficiente ya que en el peor de los casos necesitamos atravesar la matriz completa para identificar si el elemento está presente o no.

Enfoque 2:
Como la matriz está ordenada por filas y columnas, podemos aplicar la búsqueda binaria en cada fila e identificar si el elemento está presente o no.

Enfoque 3:
En este enfoque, comenzaremos nuestra búsqueda mirando el elemento más a la derecha de la primera fila.

1. If Current Element = Search element, Return True, elemento encontrado.
2. Si Elemento actual < Elemento de búsqueda, significa que todos los elementos a la izquierda del elemento actual son más pequeños y no es necesario mirar a la izquierda. Verifique el elemento en la siguiente columna.
3. Si Elemento actual> Elemento de búsqueda, significa que todos los elementos en el elemento actual debajo son más altos y no es necesario mirar hacia abajo. Verifique el elemento en el lado izquierdo en la misma fila.

Tomemos un ejemplo y comprendamos la solución:

Explicación detallada con el programa: Buscar en una matriz ordenada por filas y columnas