Playground: Search 2D Array Matrix

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

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

Comentarios

Ángel Vargas Casavantes

student•

Comparto mi intento en JS :]

function searchInMatrix(matrix, target) {
	let up = 0, left = 0;
	let down = matrix.length - 1, right = matrix[up].length - 1;
	let half, selectedRow;

	while (up <= down) { // Busqueda por columna
		half = Math.floor(up + (down - up) / 2);
		
		if (up == down) {
			selectedRow = up;
			break;
		}

		if (matrix[up][right] <= target && matrix[half][right] < target) 
			up = half+1;
		else
			down = half;
	}

	while (left <= right) { // Busqueda por fila
		half = Math.floor(left + (right - left) / 2);

		if (matrix[selectedRow][half] < target)
			left = half + 1; //: Descartamos mitad izq.
		else
			right = half - 1; //: Descartamos mitad der.

		if (matrix[selectedRow][half] == target)
			return true
	}

	return false;
}

John Eduard Meneses González

student•

Share my solution!!

Carlos Hernandez

student•

Mi solución en JS:const search2DArrayMatrix = (matrix, target) => { const rows = matrix.length; let rowsTop = 0; let rowsBottom = rows - 1; while (rowsTop <= rowsBottom) { const rowsHalf = Math.floor((rowsBottom + rowsTop) / 2); const currentRow = matrix[rowsHalf]; const currentRowLength = matrix[rowsHalf].length; // Find row if (currentRow[0] <= target && currentRow[currentRowLength - 1] >= target) { console.log('Found row that contains range'); let left = 0; let right = currentRowLength - 1; while (left <= right) { const half = Math.floor((right + left) / 2);

if (currentRow[half] === target) { console.log(Found at position: (${rowsHalf}, ${half})); return true; } if (target > currentRow[half]) { left = half + 1; } if (target < currentRow[half]) { right = half - 1; } } break; } if (target > currentRow[currentRowLength - 1]) { rowsTop = rowsHalf + 1; } if (target < currentRow[0]) { rowsBottom = rowsHalf - 1; } } return false;} const DATA_INPUT_1 = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60],]; console.log(search2DArrayMatrix(DATA_INPUT_1, 16));console.log(search2DArrayMatrix(DATA_INPUT_1, 60));console.log(search2DArrayMatrix(DATA_INPUT_1, 2));

const search2DArrayMatrix = (matrix, target) => {
    const rows = matrix.length;

    let rowsTop = 0;
    let rowsBottom = rows - 1;

    while (rowsTop <= rowsBottom) {
        const rowsHalf = Math.floor((rowsBottom + rowsTop) / 2);

        const currentRow = matrix[rowsHalf];
        const currentRowLength = matrix[rowsHalf].length;

        // Find row
        if (currentRow[0] <= target && currentRow[currentRowLength - 1] >= target) {
            console.log('Found row that contains range');
            let left = 0;
            let right = currentRowLength - 1;

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


                if (currentRow[half] === target) {
                    console.log(`Found at position: (${rowsHalf}, ${half})`);
                    return true;
                }

                if (target > currentRow[half]) {
                    left = half + 1;
                }

                if (target < currentRow[half]) {
                    right = half - 1;
                }
            }
            break;
        }
        if (target > currentRow[currentRowLength - 1]) {
            rowsTop = rowsHalf + 1;
        }
        if (target < currentRow[0]) {
            rowsBottom = rowsHalf - 1;
        }
    }

    return false;
}

const DATA_INPUT_1 = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
];

console.log(search2DArrayMatrix(DATA_INPUT_1, 16));
console.log(search2DArrayMatrix(DATA_INPUT_1, 60));
console.log(search2DArrayMatrix(DATA_INPUT_1, 2));

Bryan Castano

student•

Hello Guys, This is my Code, I took willing from some of you in the Past on your comments here bellow \n

# Search 2D Array Matrix  .....

from typing import List

def searchInMatrix(matrix: List[List[int]], Target  : int ) -> bool:

  m  = len(matrix)
  n  = len(matrix[0])
    
  left  = 0 
  right = m * n - 1
    
  while ( left <= right ) :
    
    mid = left + ( right - left ) // 2
        
    row_mid = mid // n
        
    column_mid = mid % n
        
    if  ( Target == matrix[row_mid][column_mid] )  :
        
      return True
            
    if ( Target < matrix[row_mid][column_mid]  )  : 
        
      right = mid - 1
            
    else:
        
      left  = mid + 1

  return False
  
  

matrix = [
  [1,3,5,7],
  [10,11,16,20],
  [23,30,34,60],
]

print(matrix)

response = searchInMatrix(matrix, 3)

print(response)

response2 = searchInMatrix(matrix,  12)

print(response2)

```# Search 2D Array Matrix  .....



from typing import List



def searchInMatrix(matrix: List\[List\[int]], Target  : int ) -> bool:



&#x20; m  = len(matrix)

&#x20; n  = len(matrix\[0])

&#x20;  &#x20;

&#x20; left  = 0&#x20;

&#x20; right = m \* n - 1

&#x20;  &#x20;

&#x20; while ( left <= right ) :

&#x20;  &#x20;

&#x20;   mid = left + ( right - left ) // 2

&#x20;      &#x20;

&#x20;   row\_mid = mid // n

&#x20;      &#x20;

&#x20;   column\_mid = mid % n

&#x20;      &#x20;

&#x20;   if  ( Target == matrix\[row\_mid]\[column\_mid] )  :

&#x20;      &#x20;

&#x20;     return True

&#x20;          &#x20;

&#x20;   if ( Target < matrix\[row\_mid]\[column\_mid]  )  :&#x20;

&#x20;      &#x20;

&#x20;     right = mid - 1

&#x20;          &#x20;

&#x20;   else:

&#x20;      &#x20;

&#x20;     left  = mid + 1



&#x20; return False

&#x20;&#x20;

&#x20;&#x20;



matrix = \[

&#x20; \[1,3,5,7],

&#x20; \[10,11,16,20],

&#x20; \[23,30,34,60],

]



print(matrix)



response = searchInMatrix(matrix, 3)



print(response)



response2 = searchInMatrix(matrix,  12)



print(response2)

Carlos Damián Loaiza Artunduaga

student•

Vuelvo a dejar mi solución funcional aquí:

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    n = len(matrix[0])
    i, d = 0, len(matrix) * n - 1
    while i <= d:
        mi = i + (d - i) // 2
        fmi = mi // n
        cmi = mi % n
        if target == matrix[fmi][cmi]:
            return True
        if target < matrix[fmi][cmi]:
            d = mi - 1
        else:
            i = mi + 1
    return False

Miguel Angel Reyes Moreno

student•

Comparto mi solución:

from typing import List
def searchInMatrix(matriz: List\[List\[int]], objetivo: int) -> bool:  m = len(matriz)  n = len(matriz\[0])  left = 0  right = (m\*n) - 1
&#x20; while left <= right:      k = (left + right) // 2      row = k // n      col = k % n      if matriz\[row]\[col] == objetivo:          return True #\* target is found      elif matriz\[row]\[col] < objetivo:          left = k + 1      else:          right = k - 1
&#x20; return False #\* target is not found

Nicolas Alpargatero

student•

Vengo aprender a traves de un Playground la declaración de tipo de variables, super útil, porque yo creaba variable auxiliar para darle dir() y help() jajaj

. . .

function searchInMatrix(matrix, target) {
	let up = 0, left = 0;
	let down = matrix.length - 1, right = matrix[up].length - 1;
	let half, selectedRow;

	while (up <= down) { // Busqueda por columna
		half = Math.floor(up + (down - up) / 2);
		
		if (up == down) {
			selectedRow = up;
			break;
		}

		if (matrix[up][right] <= target && matrix[half][right] < target) 
			up = half+1;
		else
			down = half;
	}

	while (left <= right) { // Busqueda por fila
		half = Math.floor(left + (right - left) / 2);

		if (matrix[selectedRow][half] < target)
			left = half + 1; //: Descartamos mitad izq.
		else
			right = half - 1; //: Descartamos mitad der.

		if (matrix[selectedRow][half] == target)
			return true
	}

	return false;
}

const search2DArrayMatrix = (matrix, target) => {
    const rows = matrix.length;

    let rowsTop = 0;
    let rowsBottom = rows - 1;

    while (rowsTop <= rowsBottom) {
        const rowsHalf = Math.floor((rowsBottom + rowsTop) / 2);

        const currentRow = matrix[rowsHalf];
        const currentRowLength = matrix[rowsHalf].length;

        // Find row
        if (currentRow[0] <= target && currentRow[currentRowLength - 1] >= target) {
            console.log('Found row that contains range');
            let left = 0;
            let right = currentRowLength - 1;

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


                if (currentRow[half] === target) {
                    console.log(`Found at position: (${rowsHalf}, ${half})`);
                    return true;
                }

                if (target > currentRow[half]) {
                    left = half + 1;
                }

                if (target < currentRow[half]) {
                    right = half - 1;
                }
            }
            break;
        }
        if (target > currentRow[currentRowLength - 1]) {
            rowsTop = rowsHalf + 1;
        }
        if (target < currentRow[0]) {
            rowsBottom = rowsHalf - 1;
        }
    }

    return false;
}

const DATA_INPUT_1 = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
];

console.log(search2DArrayMatrix(DATA_INPUT_1, 16));
console.log(search2DArrayMatrix(DATA_INPUT_1, 60));
console.log(search2DArrayMatrix(DATA_INPUT_1, 2));

# Search 2D Array Matrix  .....

from typing import List

def searchInMatrix(matrix: List[List[int]], Target  : int ) -> bool:

  m  = len(matrix)
  n  = len(matrix[0])
    
  left  = 0 
  right = m * n - 1
    
  while ( left <= right ) :
    
    mid = left + ( right - left ) // 2
        
    row_mid = mid // n
        
    column_mid = mid % n
        
    if  ( Target == matrix[row_mid][column_mid] )  :
        
      return True
            
    if ( Target < matrix[row_mid][column_mid]  )  : 
        
      right = mid - 1
            
    else:
        
      left  = mid + 1

  return False
  
matrix = [
  [1,3,5,7],
  [10,11,16,20],
  [23,30,34,60],
]

print(matrix)

response = searchInMatrix(matrix, 3)

print(response)

response2 = searchInMatrix(matrix,  12)

print(response2)

```# Search 2D Array Matrix  .....

from typing import List

def searchInMatrix(matrix: List\[List\[int]], Target  : int ) -> bool:

&#x20; m  = len(matrix)

&#x20; n  = len(matrix\[0])

&#x20;  &#x20;

&#x20; left  = 0&#x20;

&#x20; right = m \* n - 1

&#x20;  &#x20;

&#x20; while ( left <= right ) :

&#x20;  &#x20;

&#x20;   mid = left + ( right - left ) // 2

&#x20;      &#x20;

&#x20;   row\_mid = mid // n

&#x20;      &#x20;

&#x20;   column\_mid = mid % n

&#x20;      &#x20;

&#x20;   if  ( Target == matrix\[row\_mid]\[column\_mid] )  :

&#x20;      &#x20;

&#x20;     return True

&#x20;          &#x20;

&#x20;   if ( Target < matrix\[row\_mid]\[column\_mid]  )  :&#x20;

&#x20;      &#x20;

&#x20;     right = mid - 1

&#x20;          &#x20;

&#x20;   else:

&#x20;      &#x20;

&#x20;     left  = mid + 1

&#x20; return False

&#x20;&#x20;

&#x20;&#x20;

matrix = \[

&#x20; \[1,3,5,7],

&#x20; \[10,11,16,20],

&#x20; \[23,30,34,60],

]

print(matrix)

response = searchInMatrix(matrix, 3)

print(response)

response2 = searchInMatrix(matrix,  12)

print(response2)

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    n = len(matrix[0])
    i, d = 0, len(matrix) * n - 1
    while i <= d:
        mi = i + (d - i) // 2
        fmi = mi // n
        cmi = mi % n
        if target == matrix[fmi][cmi]:
            return True
        if target < matrix[fmi][cmi]:
            d = mi - 1
        else:
            i = mi + 1
    return False

from typing import List
def searchInMatrix(matriz: List\[List\[int]], objetivo: int) -> bool:  m = len(matriz)  n = len(matriz\[0])  left = 0  right = (m\*n) - 1
&#x20; while left <= right:      k = (left + right) // 2      row = k // n      col = k % n      if matriz\[row]\[col] == objetivo:          return True #\* target is found      elif matriz\[row]\[col] < objetivo:          left = k + 1      else:          right = k - 1
&#x20; return False #\* target is not found

Playground: Search 2D Array Matrix

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena

Combinar Listas Ordenadas en un Array Ascendente

Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Playground: Merge Two Sorted Lists

Intercalación de Listas Ordenadas en Python

Resolver el problema "Container with Most Water" en Python

Cálculo Óptimo de Área en Listas de Alturas

Playground: Container with Most Water

Implementación de solución de cálculo de área máxima en Java

Implementación de Trapping Rainwater en Complejidad Lineal

Retos de Algoritmos con Apuntadores en Python

Patrones de Dos Apuntadores: Soluciones a Problemas Comunes en Python

Ventana Deslizante

Patrón Ventana Deslizante para Análisis de Datos Secuenciales

Subcadena más larga sin caracteres repetidos: patrón ventana deslizante

Algoritmo de Ventana Deslizante para Subcadenas Únicas

Playground: Longest Substring Without Repeating Characters

Algoritmo Python para Substring más Largo Sin Repeticiones

Retos de Algoritmos: Dos Apuntadores y Subcadenas

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Búsqueda Binaria

Algoritmo de búsqueda binaria en listas ordenadas

Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada

Búsqueda Binaria en Arreglos Rotados

Playground: Search in Rotated Arrays

Búsqueda en Arrays Rotados con C++

Búsqueda eficiente en matriz ordenada MxN

Búsqueda Binaria en Matrices 2D Ordenadas

Playground: Search 2D Array Matrix

Búsqueda Binaria en Matrices con Python

Próximos pasos

Estructuras de Datos Lineales: Conceptos y Aplicaciones