LeetCode – Buscar una matriz 2D (Java)

Escriba un algoritmo eficiente que busque un valor en una matriz mxn. Esta matriz tiene propiedades:

1) Los números enteros de cada fila se ordenan de izquierda a derecha. 2) El primer número entero de cada fila es mayor que el último número entero de la fila anterior.

Por ejemplo, considere la siguiente matriz:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Dado el objetivo = 3, devuelve verdadero.

Solución Java

Este es un problema típico de la búsqueda binaria.

Puede intentar resolver este problema encontrando primero la fila y luego la columna. No es necesario hacer eso. Debido a las características especiales de la matriz, la matriz se puede considerar como una matriz ordenada. El objetivo es encontrar el elemento en esta matriz ordenada mediante la búsqueda binaria.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) 
            return false;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int start = 0;
        int end = m*n-1;
 
        while(start<=end){
            int mid=(start+end)/2;
            int midX=mid/n;
            int midY=mid%n;
 
            if(matrix[midX][midY]==target) 
                return true;
 
            if(matrix[midX][midY]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
 
        return false;
    }
}