Búsqueda Binaria en Matrices con Python

Clase 34 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cómo buscar un elemento en una matriz usando búsqueda binaria en Python?

Bienvenidos a esta clase del curso de Platzi, donde exploraremos cómo solucionar el problema "Search into DRA Matrix" utilizando búsqueda binaria en Python. Vamos a abordar este desafío paso a paso, entender cómo implementar la solución y reconocer la eficiencia del algoritmo.

¿Cuál es el problema que estamos resolviendo?

El objetivo de este ejercicio es determinar si un elemento se encuentra en una matriz dada. A diferencia de ejercicios anteriores donde se requería devolver una posición, aquí debemos regresar simplemente True o False. La premisa es realizar una búsqueda binaria en la matriz, explorando primero las columnas y luego las filas, de manera óptima.

¿Cómo se implementa la búsqueda binaria en columnas y filas?

El proceso incluye dos etapas principales de búsqueda binaria: horizontal (columnas) y vertical (filas). Empecemos con el código:

def search_in_matrix(matrix, target):
    # Inicializamos apuntadores para la izquierda y la derecha
    left = 0
    right = len(matrix) - 1

    # Primero, identificación de la columna
    while left <= right:
        mid = left + (right - left) // 2
        if matrix[mid][0] == target:
            return True
        elif matrix[mid][0] < target:
            left = mid + 1
        else:
            right = mid - 1

    # Ahora buscamos en la fila identificada
    row = matrix[right]
    left, right = 0, len(row) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if row[mid] == target:
            return True
        elif row[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # Caso base, si el elemento no fue encontrado
    return False

Este código ilustra cómo se logra la búsqueda en dos etapas, primero ajustando los apuntadores para las columnas y luego para una fila específica, bajo el paradigma de búsqueda binaria.

¿Qué debemos considerar sobre la complejidad?

La búsqueda binaria es conocida por su eficiencia. En este caso particular:

Complejidad Temporal: La búsqueda binaria en columnas y filas resulta en una complejidad de O(log n), donde n es el número de elementos en la matriz.
Complejidad Espacial: O(1), ya que solo utilizamos un número constante de variables, independientemente del tamaño de los datos de entrada.

¿Qué hace única esta implementación?

Lo que hace particularmente interesante esta solución es el doble uso de la búsqueda binaria, una vez horizontal y otra vertical, permitiendo encontrar un elemento específico de manera muy eficiente en una matriz ordenada. Además, esta metodología es extensible y puede ser implementada en otros lenguajes de programación según las necesidades del desarrollador.

Siéntanse motivados a probar sus propias soluciones, quizás en otros lenguajes, o con pequeñas modificaciones para adaptarlas a diferentes escenarios. La práctica y experimentación son claves en este camino de aprendizaje continuo sobre estructuras de datos y algoritmos. ¡Los alentamos a seguir explorando y perfeccionando sus habilidades en programación!

César Rincón Muñoz

student•

En los primeros ejemplos tardé más de 4 horas intentadolo, aún así no lograba llegar a la solución. Pero la constancia y el esfuerzo siempre trae resultados.

Comprendí la lógica del Patrón, y en este ejemplo logré llegar a una solución sencilla, eficiente y elegante.

Me alegra poder compartirla, está escrita en JS:

const search2dArray = (arr, target) => {
    let p1 = 0
    let p2 = arr[p1].length -1
    let mit
    
    while (p1 <= p2 && p1 <= arr.length-1) {
        mit = arr[p1][p2]
        console.log(`p1 = ${p1}, p2 = ${p2}, mit = ${mit}`)
        if (mit == target) return true
        if (mit < target) {
            p1++
        } else {
            p2--
        }
    }
    return false
}

Nicolas Alpargatero

student•

Realmente el código de la profe no esta mal, es el que copio en recursos el que tiene un bug y es derecha = len(matriz[0]) - 1 debe ser como en el video derecha = len(matriz) - 1

Diego Herrera Prado

student•

Comparto mi solución en python

from typing import List

def searchInMatrix(matriz: List[List[int]], objetivo: int) -> bool:
  left = 0
  right = len(matriz[0])-1
  middle_col = 0
  top = 0
  bottom = len(matriz)-1
  middle_row = 0

  while(top<=bottom):
    middle_row = top + (bottom-top)//2
    
    if middle_row == bottom or middle_row == top:
      break

    if matriz[middle_row][-1] > objetivo:
      bottom = middle_row - 1
    else:
      top = middle_row + 1
  
  while(left<=right):
    middle_col = left + (right-left)//2
    if matriz[middle_row][middle_col] == objetivo:
      return True
    
    if matriz[middle_row][middle_col]>objetivo:
      right = middle_col - 1
    else:
      left = middle_col +1
  
  return False

matriz = [
  [1,3,5,7],
  [10,11,16,20],
  [23,30,34,60],
]
print(matriz)

response = searchInMatrix(matriz, 3)
print(response)

response2 = searchInMatrix(matriz, 12)
print(response2)

Emilio Sala

student•

Si buscas cualquier numero de la fila [10,11,16,20] nunca los encuentra El codigo de la profesora tampoco funciona como debería Creo que con esta condición ya regresas la fila central en tu código

  while(top<=bottom):
    middle_row = top + (bottom-top)//2
    if matriz[middle_row][0] == objetivo:
      return True
    if matriz[middle_row][0] < objetivo and matriz[bottom][0] > objetivo:
      break
    if matriz[middle_row][-1] > objetivo:
      bottom = middle_row - 1
    else:
      top = middle_row + 1

John Eduard Meneses González

student•

share my solution!!

Carlos Castro

student•

Tuve problemas para diferenciar entre si agregar el +1 o no al calcular la mitad. Pero al fin pude adaptar la solución de la maestra a JavaScript:

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    var left = 0;
    var right = matrix.length - 1;
    var mid, row;

    while (left < right) {
        mid = Math.floor((left + right) / 2) + 1;

        if (target === matrix[mid][0]) {
            return true;
        }

        if (matrix[mid][0] < target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    row = matrix[left];
    left = 0; right = row.length - 1;

    while (left <= right) {
        mid = Math.floor ((left + right) / 2);

        if (target === row[mid]) {
            return true;
        }

        if (row[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }

    }
    return false;
};
```/\*\* \* @param {number\[]\[]} matrix \* @param {number} target \* @return {boolean} \*/var searchMatrix = function(matrix, target) {    var left = 0;    var right = matrix.length - 1;    var mid, row;
&#x20;   while (left < right) {        mid = Math.floor((left + right) / 2) + 1;
&#x20;       if (target === matrix\[mid]\[0]) {            return true;        }
&#x20;       if (matrix\[mid]\[0] < target) {            left = mid;        } else {            right = mid - 1;        }    }
&#x20;   row = matrix\[left];    left = 0; right = row.length - 1;
&#x20;   while (left <= right) {        mid = Math.floor ((left + right) / 2);
&#x20;       if (target === row\[mid]) {            return true;        }
&#x20;       if (row\[mid] < target) {            left = mid + 1;        } else {            right = mid - 1;        }
&#x20;   }    return false;};

Angélica María Celis Torres

student•

Pensando la matrix como un array continuo de mn elementos se puede lograr una complejidad O(log nm). Para hallar los indices [ i ][ j ] donde se ubicaria la mitad en la matrix podemos usar i = mid/n y j = mid%n. Este es el codigo en c++.

Mi primer intento fue algo mas intuitivo pero tiene una complejidad mas alta O(m log n). Este es el codigo de esa solucion.

```js bool searchMatrix(std::vector<std::vector<int>>& matrix, int target){ //m rows n colums int m, n, left, right;

m = matrix.size();
n = matrix[0].size();

left = 0;
right = n - 1;

for(int i = 0; i < m ; i++){
    if(matrix[i][left] <= target && target <= matrix[i][right]){
        while(left <= right){
            int mid = (left+right)/2;
            if(target == matrix[i][mid]){
                return true;
            }else if(target < matrix[i][mid]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return false;
    }
}

return false;

}

Hans Arias

student•

Fue un gran ejercicio, en algunas veces, se convirtió en un ciclo infinito, pero era porque no maneje bien la parte de Derecha, necesitaba disminuir.

Este es mi código hecho en Java


public class SearchArray2D {

    /*+ Target = 2
    row 0 col 0 1
    row 0 col 1 3
    row 0 col 2 5
    row 1 col 0 10
    row 1 col 1 11
    row 1 col 2 16
     */
    public int [] getIndex (int[][] numbers, int target) {

        int currentPositionRow = 0; //
        int sizeOfColumn = numbers[0].length - 1; // 2

        boolean approximate = false;

        while (currentPositionRow < numbers.length) {
            int firstItem = numbers[currentPositionRow][0]; // 1
            int lastItem = numbers[currentPositionRow][sizeOfColumn]; // 5

            // 1 == 2 || 5 == 2
            if (firstItem == target || lastItem == target) {
                return new int[] {currentPositionRow, firstItem == target ? 0: sizeOfColumn};
            } else if (target > firstItem && target < lastItem) { // 2 > 1 && 2 < 5
                approximate = true;
                break;
            } else {
                currentPositionRow++; // 1
            }
        }

        if (!approximate) return new int[] {-1};

        int low = 0;
        int high = sizeOfColumn; // 0
        int half;

        // 0 <= -1 exit of loop
        while (low <= high) {
            // 0 + (0 - 0) / 2 = 0
            half = low + (high - low) / 2; // 0

            // 1 == 2
            if (numbers[currentPositionRow][half] == target) return new int[] {currentPositionRow, half};

            // 1 < 2
            if (numbers[currentPositionRow][half] < target) {
                low = half+1;
            } else {
                high = half -1; // high = -1
            }
        }

        return new int[] {-1}; // return this.
    }

}

Estos son mis test unitarios.


import static org.junit.jupiter.api.Assertions.assertEquals;

public class SearchArray2DTest {

    private SearchArray2D searchArray2D = new SearchArray2D();

    @Test
    public void shouldGetPositionSinceTenIsLocatedOnTheSecondRecordLikeFirstItem () {
        int[][] numbers = new int[][] { {1,3, 5}, {10, 11, 16} };
        int target = 10;

        int[] response = searchArray2D.getIndex(numbers, target);

        assertEquals(2, response.length);
        assertEquals(1, response[0]);
        assertEquals(0, response[1]);
    }

    @Test
    public void shouldGetPositionSinceElevenIsLocatedOnTheSecondRecordLikeHalf () {
        int[][] numbers = new int[][] { {1,3, 5}, {10, 11, 16} };
        int target = 11;

        int[] response = searchArray2D.getIndex(numbers, target);

        assertEquals(2, response.length);
        assertEquals(1, response[0]);
        assertEquals(1, response[1]);
    }

    @Test
    public void shouldGetNegativeOneSinceTwentyIsGreaterThanLastItemOfList () {
        int[][] numbers = new int[][] { {1,3, 5}, {10, 11, 16} };
        int target = 20;

        int[] response = searchArray2D.getIndex(numbers, target);

        assertEquals(1, response.length);
        assertEquals(-1, response[0]);
    }


    @Test
    public void shouldGetNegativeOneSinceTwelveIsNotExistIntoList () {
        int[][] numbers = new int[][] { {1,3, 5}, {10, 11, 16} };
        int target = 12;

        int[] response = searchArray2D.getIndex(numbers, target);

        assertEquals(1, response.length);
        assertEquals(-1, response[0]);
    }

    @Test
    public void shouldGetNegativeOneSinceTwoIsNotExistIntoList () {
        int[][] numbers = new int[][] { {1,3, 5}, {10, 11, 16} };
        int target = 2;

        int[] response = searchArray2D.getIndex(numbers, target);

        assertEquals(1, response.length);
        assertEquals(-1, response[0]);
    }

}

Valeria Rubio Herrera

student•

var searchMatrix = function(matrix, target) {
  let rows=matrix.length;
  let columns = matrix[0].length;
  let low=0;
  let high=rows*columns-1;
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
    return false;
  }
  while(low<=high){
    const mid = Math.floor((high+low)/2);
    const midValue = matrix[Math.floor(mid/columns)][mid%columns]
    if(midValue===target){ //indexes
      return true;
    }else if(midValue>=target){
      high= mid-1;
    }else{
      low = mid+1;
    }
  }
  return false;
};
```var searchMatrix = function(matrix, target) {  let rows=matrix.length;  let columns = matrix\[0].length;  // console.log(rows)  // console.log(columns)  let low=0;  let high=rows\*columns-1;  if (!matrix || matrix.length === 0 || matrix\[0].length === 0) {    return false;  }  while(low<=high){    const mid = Math.floor((high+low)/2);    const midValue = matrix\[Math.floor(mid/columns)]\[mid%columns]    if(midValue===target){ //indexes      return true;    }else if(midValue>=target){      high= mid-1;    }else{      low = mid+1;    }    //mid = Math.floor((high+low)/2);  }  return false;};

Manuel Alejandro Perdomo

student•

Yo primero opté por hallar el rango del target verificando el inicio y final de cada elemento dentro del array despues de hallar un posible intervalo, aplico la busqueda binaria.

function findArrayMatriz(matrix,target){
    let left = 0;
    let right = 0;
    let arr = [];

    for (let i = 0; i < matrix.length; i++) {
        left = 0
        right = matrix[i].length - 1;
        arr = matrix[i];
        console.log('loop: ',i, ' p1: ',left,' p2: ',right,' target1: ',arr[left],' target2: ',arr[right])
        if(target >= arr[left] && target <= arr[right]){
            while(left <= right){
                half =  Math.floor((left + right)/2)
                if(arr[half] == target){
                    return true;
                }
                if(target >= arr[half] && target <= arr[right]){
                    left = half + 1;
                } else {
                    right = half -1;
                }
            }
        }
    }

    return false;
}

Nicolas Alpargatero

student•

Valido pero es O(n log m), la profe enseña con O(log nm) que es incluso mejor que O(nm)

Carlos Raúl Romero Martínez

student•

Si puede resolver con una sola búsqueda binaría, con complejidad log(nm), supongamos que tenemos una matriz n = 3 y m=5, entonces la posición 0,0 seria 0 búsqueda binaria y la posición n-1,m-1 , seria (nm)-1,se buscaría de 0 a (nm)-1, se ocuparía otra función para convertir los numero en posiciones , la cual tendría un complejidad de log(1) ya que solo sería una operación. ejemplo [0 ,1 ,2 ,3 ,4 ] [5 ,6 ,7 ,8 ,9 ] [10,11,12,13,14] [15,16,17,18,19]

Luis Sandoval

student•

Esta es mi posible solucion:

    public static bool Search(int[,] nums, int target)
    {
        var left = 0;
        var right = nums.GetLength(1) - 1;

        while (left < right)
        {
            if (nums[left, right] < target)
            {
                left++;
                continue;
            }

            if (nums[left, 0] > target) return false;

            break; // ENCONTRE DONDE PUEDE ESTAR
        }

        int row = left;
        left = 0;



        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            if (nums[row, middle] == target) return true;

            if (nums[row, middle] < target) left = middle + 1;
            else right = middle - 1;
        }

        return false;
    }```

Christopher Andrés Guano Valencia

student•

👨‍💻Solución en JavaScript / TypeScript

Comparto otra solución con complejidad espacial O(1), a diferencia de la clase que fue O(fila). . Search 2D Array Matrix

Felipe Guzmán - Bautista

student•

Solution en Python Con opción de búsqueda a fuerza bruta o con búsqueda binaria

def solve_brute_force(n_matrix, n_target):
    for row_i in range(0, len(n_matrix)):
        row = n_matrix[row_i]
        for col_i in range(0, len(row)):
            col = row[col_i]
            if col == n_target:
                return (row_i, col_i)

def binary_seach(n_list, n_target):
    right_padding = 0 
    split_pos = len(n_list) // 2 
    i = 0 
    while True: 
        split_pos = len(n_list) // 2 
        left, right = n_list[0:split_pos], n_list[split_pos:]
        if left[0] <= n_target and n_target <= left[-1]: 
            if left[0] == n_target: 
                return right_padding + 1
            elif left[-1] == n_target:
                return right_padding + len(left) - 1
            else:
                n_list = left 
        elif right[0] <= n_target and n_target <= right[-1]:
            right_padding += len(left)
            if right[0] == n_target: 
                return right_padding + 1
            elif right[-1] == n_target: 
                return right_padding + len(right) - 1
            else:
                n_list = right
        else: 
            return -1 

def solve_binary_search(n_matrix, n_target):
    rows = [i for i in range(0, len(n_matrix)) if n_matrix[i][0] <= n_target and n_target <= n_matrix[i][-1]]
    for row_i in rows: 
        row = n_matrix[row_i]
        col_i = binary_seach(row, n_target)
        return row_i, col_i
    return -1, -1