problems/search-in-a-row-wise-and-column-wise-sorted-matrix.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "d49b30bf",
   "metadata": {},
   "source": [
    "# Buscar un elemento en una matriz ordenada por filas y columnas\n",
    "\n",
    "> Más conocido como: Search in a Row-wise and Column-wise Sorted Matrix  \n",
    "Algoritmo: Búsqueda por Eliminación  \n",
    "Complejidad del tiempo: O(n + m)  \n",
    "Complejidad del espacio: O(1)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "cc6ee269",
   "metadata": {},
   "source": [
    "## Problema\n",
    "Dada una matriz 2D ordenada en la que cada fila y cada columna están ordenadas en orden ascendente, se busca encontrar la posición de un elemento dado en la matriz.\n",
    "\n",
    "## Ejemplo"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "979ca739",
   "metadata": {},
   "source": [
    "<pre>\n",
    "Matriz dada:\n",
    "\n",
    "      +----+----+----+----+\n",
    "      | 11 | 18 | 31 | 42 |\n",
    "      +----+----+----+----+\n",
    "      | 14 | 22 | 34 | 47 |\n",
    "      +----+----+----+----+\n",
    "      | 23 | 25 | 37 | 49 |\n",
    "      +----+----+----+----+\n",
    "      | 33 | 36 | 39 | 55 |\n",
    "      +----+----+----+----+\n",
    "\n",
    "Buscar el elemento 25.\n",
    "Resultado: El elemento 25 se encuentra en la fila 3, columna 2.\n",
    "</pre>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "5a587e06",
   "metadata": {},
   "source": [
    "## Solución\n",
    "La solución a este problema se basa en un enfoque de **búsqueda por eliminación** que aprovecha la ordenación de las filas y columnas de la matriz. Dado que la matriz está ordenada tanto por filas como por columnas, podemos comenzar la búsqueda desde una esquina de la matriz (por ejemplo, la esquina superior derecha o la inferior izquierda) y eliminar filas o columnas en cada paso, dependiendo de cómo se compare el elemento objetivo con el elemento en la posición actual.   \n",
    "Este método es eficiente ya que en cada paso se descarta al menos una fila o una columna, llevando a una complejidad de tiempo lineal en términos del tamaño de la matriz.\n",
    "\n",
    "### Pseudocódigo"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "577dfb9e",
   "metadata": {},
   "source": [
    "<pre>\n",
    "Inicio\n",
    "   Seleccionar la esquina superior derecha como punto de partida\n",
    "   Mientras que el elemento no sea encontrado\n",
    "      Si el elemento es mayor, moverse hacia abajo\n",
    "      Si el elemento es menor, moverse hacia la izquierda\n",
    "Fin\n",
    "</pre>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a254a1fa",
   "metadata": {},
   "source": [
    "### Implementación del Algoritmo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f285ba8c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "El elemento 25 se encuentra en la fila 3, columna 2.\n"
     ]
    }
   ],
   "source": [
    "def buscarEnMatriz(matriz, elemento):\n",
    "    filas = len(matriz)\n",
    "    columnas = len(matriz[0]) if filas > 0 else 0\n",
    "    fila = 0\n",
    "    columna = columnas - 1\n",
    "\n",
    "    while fila < filas and columna >= 0:\n",
    "        if matriz[fila][columna] == elemento:\n",
    "            return (fila, columna)\n",
    "        elif matriz[fila][columna] < elemento:\n",
    "            fila += 1\n",
    "        else:\n",
    "            columna -= 1\n",
    "\n",
    "    return (-1, -1)\n",
    "\n",
    "# Ejemplo de uso\n",
    "matriz = [\n",
    "    [11, 18, 31, 42],\n",
    "    [14, 22, 34, 47],\n",
    "    [23, 25, 37, 49],\n",
    "    [33, 36, 39, 55]\n",
    "]\n",
    "\n",
    "elemento = 25\n",
    "posicion = buscarEnMatriz(matriz, elemento)\n",
    "\n",
    "if posicion != (-1, -1):\n",
    "    print(f\"El elemento {elemento} se encuentra en la fila {posicion[0] + 1}, columna {posicion[1] + 1}.\")\n",
    "else:\n",
    "    print(\"El elemento no se encuentra en la matriz.\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ac8de189",
   "metadata": {},
   "source": [
    "### Explicación Paso a Paso\n",
    "- **Inicio en la esquina**: Comenzamos en la esquina superior derecha de la matriz. Esta posición nos permite mover hacia la izquierda si el elemento actual es mayor que el objetivo y hacia abajo si es menor.\n",
    "- **Comparación y movimiento**: En cada paso, comparamos el elemento de la matriz en nuestra posición actual con el elemento objetivo.\n",
    "  - Si el elemento de la matriz es mayor que el objetivo, nos movemos hacia la izquierda, ya que todos los elementos a la derecha serán mayores y no necesitamos considerarlos.\n",
    "  - Si el elemento de la matriz es menor que el objetivo, nos movemos hacia abajo, ya que todos los elementos arriba serán menores y no necesarios para la búsqueda.\n",
    "- **Encontrar o descartar**: Este proceso continúa hasta que encontramos el elemento o hasta que los índices salen de los límites de la matriz, lo que indica que el elemento no está presente.\n",
    "\n",
    "### Tracing\n",
    "\n",
    "| Paso | Posición (fila, columna) | Valor en Posición | Acción          |\n",
    "| ---- | ------------------------ | ----------------- | --------------- |\n",
    "| 1    | (0, 3)                   | 42                | Mover izquierda |\n",
    "| 2    | (0, 2)                   | 31                | Mover izquierda |\n",
    "| 3    | (0, 1)                   | 18                | Mover abajo     |\n",
    "| 4    | (1, 1)                   | 22                | Mover abajo     |\n",
    "| 5    | (2, 1)                   | 25                | Encontrado      |\n",
    "\n",
    "La tabla de trazas muestra cómo cambian los índices de fila y columna a medida que buscamos el elemento 25 en la matriz. Comenzamos desde la esquina superior derecha y nos movemos hacia la izquierda o hacia abajo basándonos en la comparación del valor en la posición actual con el valor objetivo. El proceso termina cuando encontramos el elemento 25 en la posición (2, 1), que corresponde a la fila 3 y columna 2, si contamos desde 1.\n",
    "\n",
    "## Puntos clave\n",
    "\n",
    "- **Inicio en la Esquina Superior Derecha**: Comenzar la búsqueda desde la esquina superior derecha (o inferior izquierda, dependiendo de la implementación) es crucial porque permite dos opciones claras de movimiento (hacia la izquierda o hacia abajo) basadas en la comparación del valor actual con el objetivo. Esta posición estratégica hace uso de la propiedad única de la matriz ordenada por filas y columnas para descartar eficientemente grandes secciones de la matriz en cada paso.\n",
    "\n",
    "- **Eliminación Progresiva**: A medida que avanzamos en la matriz, eliminamos sistemáticamente filas o columnas que sabemos que no pueden contener el elemento objetivo. Esto es posible gracias a la ordenación de la matriz, lo que garantiza que, si nos movemos hacia la izquierda, todos los elementos a la derecha del punto actual pueden ser ignorados, y si nos movemos hacia abajo, todos los elementos por encima del punto actual ya no son relevantes.\n",
    "\n",
    "- **Sin Uso de Espacio Extra**: La belleza de este algoritmo radica en su simplicidad y eficiencia, ya que opera directamente sobre la matriz dada sin necesidad de estructuras de datos adicionales. Esto mantiene la complejidad del espacio en O(1), un aspecto importante para la eficiencia de la memoria.\n",
    "\n",
    "- **Eficiencia en el Peor de los Casos**: Aunque la complejidad del tiempo es O(n + m), donde `n` es el número de filas y `m` el de columnas, este enfoque es notablemente eficiente en práctica. En el peor de los casos, la búsqueda se realiza a través de una fila completa y una columna completa, pero la eliminación progresiva de opciones reduce significativamente el espacio de búsqueda en cada paso.\n",
    "\n",
    "- **Universalidad del Método**: Este método no se limita a matrices cuadradas, sino que se aplica igualmente bien a matrices rectangulares. La clave es la propiedad de ordenamiento, no las dimensiones exactas de la matriz.\n",
    "\n",
    "- **Adaptabilidad**: Aunque el algoritmo se describe para comenzar en la esquina superior derecha, podría adaptarse fácilmente para comenzar en la esquina inferior izquierda, moviéndose hacia arriba en lugar de hacia abajo y hacia la derecha en lugar de hacia la izquierda, dependiendo de la disposición específica y las propiedades de ordenamiento de la matriz en cuestión.\n",
    "\n",
    "Estos puntos clave subrayan la elegancia y la eficacia del algoritmo de búsqueda en matrices ordenadas por filas y columnas, destacando cómo se puede lograr una búsqueda rápida y eficiente aprovechando las propiedades estructurales de la matriz.\n",
    "\n",
    "## Complejidad\n",
    "\n",
    "- **Complejidad del tiempo: O(n + m)**: Donde `n` es el número de filas y `m` el de columnas. En el peor de los casos, podemos recorrer una fila completa y una columna completa.\n",
    "- **Complejidad del espacio: O(1)**: No se utiliza espacio adicional significativo; solo se requieren variables para almacenar índices y realizar comparaciones.\n",
    "\n",
    "En resumen, este algoritmo ofrece una manera eficiente de buscar un elemento en una matriz ordenada por filas y columnas, aprovechando su estructura ordenada para realizar la búsqueda de manera óptima.\n",
    "\n",
    "## Nemotécnicos\n",
    "\n",
    "- **Del Borde al Núcleo**: Inicia la búsqueda desde la esquina superior derecha, un punto estratégico que establece una ruta directa de acción. Si el número actual es mayor que el objetivo, desplázate hacia la izquierda. Si es menor, avanza hacia abajo. Este enfoque simplifica el proceso de eliminación, guiándote eficientemente hacia el valor buscado.\n",
    "- **Navegación por Brújula**: Imagina que tienes una brújula en esta matriz, donde el norte te lleva hacia abajo (a números mayores) y el oeste te lleva hacia la izquierda (hacia números menores). Tu objetivo es encontrar el tesoro (el elemento buscado) utilizando la menor cantidad de pasos posible. Este enfoque de \"navegar\" por la matriz te ayuda a recordar que debes ajustar tu dirección basándote en la comparación del valor actual con tu destino, asegurando una búsqueda eficiente y directa.\n",
    "\n",
    "## Ideas\n",
    "\n",
    "- **Extensión a Matrices No Cuadradas**: Este algoritmo funciona igual de bien en matrices no cuadradas. La clave es la ordenación por filas y columnas, no las dimensiones de la matriz.\n",
    "- **Búsqueda en 3D**: Una idea fascinante sería extender este concepto a estructuras de datos tridimensionales, donde cada \"capa\" es una matriz 2D ordenada. Los movimientos serían más complejos pero basados en el mismo principio de eliminación.\n",
    "\n",
    "## Anécdotas\n",
    "\n",
    "- **Un Problema de Entrevista Común**: Este problema es un favorito en entrevistas de programación, ya que pone a prueba la comprensión de los candidatos sobre las estructuras de datos, algoritmos y su capacidad para aplicar el razonamiento lógico en situaciones complejas.\n",
    "- **Historia de la Matriz Ordenada**: Las matrices ordenadas han sido una herramienta fundamental en la computación desde sus inicios. La habilidad para buscar eficientemente en ellas ha impulsado el desarrollo de algoritmos como este, demostrando la importancia de estructuras de datos bien organizadas en la informática.\n",
    "\n",
    "## Resumen\n",
    "\n",
    "Buscar un elemento en una matriz ordenada por filas y columnas es un problema clásico que demuestra el poder de la eliminación y la búsqueda inteligente. Utilizando un enfoque que aprovecha la ordenación de la matriz, es posible encontrar el elemento deseado con una eficiencia notable, logrando una complejidad de tiempo lineal respecto al tamaño de la matriz. Este método es intuitivo, una vez que se entiende el principio de \"Menor abajo, Mayor izquierda\", y puede ser aplicado con poca modificación a problemas similares, incluyendo estructuras de datos más complejas.\n",
    "\n",
    "Este problema no solo es un ejercicio académico útil sino también una herramienta práctica en el arsenal de cualquier programador, ofreciendo una lección valiosa en la eficiencia algorítmica y el diseño de soluciones inteligentes para problemas comunes de búsqueda y ordenamiento.\n",
    "\n",
    "## Temas de estudio\n",
    "\n",
    "Para abordar el problema de \"Buscar un elemento en una matriz ordenada por filas y columnas\", te sugiero revisar los siguientes temas:\n",
    "\n",
    "- [Algoritmos Básicos de Búsqueda: Búsqueda Binaria](../notebook/algoritmos-basicos-de-busqueda/busqueda-binaria.ipynb) para entender cómo se puede optimizar la búsqueda en estructuras ordenadas.\n",
    "\n",
    "- [Implementación de Estructuras de Datos en Python: Comparación entre las Estructuras de Datos Nativas y su Implementación en Python](../notebook/implementacion-de-estructuras-de-datos-en-python/comparacion-entre-las-estructuras-de-datos-nativas-y-su-implementacion-en-python.ipynb) para comprender cómo se manejan internamente las matrices (listas de listas) en Python.\n",
    "\n",
    "Considera también revisar conceptos básicos sobre matrices y operaciones con ellas para tener una base sólida:\n",
    "\n",
    "- [Estructuras de Datos Nativas de Python: Listas](../notebook/estructuras-de-datos-nativas-de-python/listas.ipynb), ya que las matrices en Python se pueden representar como listas de listas.\n",
    "\n",
    "- [Anexos: For en Profundidad](../notebook/anexos/anexo-0-for-en-profundidad.ipynb) para mejorar tu comprensión sobre cómo iterar eficientemente a través de estructuras de datos complejas como las matrices."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}