¿Cómo busco un número en una matriz 2d ordenada de izquierda a derecha y de arriba a abajo?

Recientemente me dieron esta pregunta de la entrevista y tengo curiosidad por saber cuál sería una buena solución.

Digamos que me dan una matriz 2d donde todos los números de la matriz están en orden creciente de izquierda a derecha y de arriba a abajo.

¿Cuál es la mejor manera de buscar y determinar si un número objetivo está en la matriz?

Ahora, mi primera inclinación es utilizar una búsqueda binaria ya que mis datos están ordenados. Puedo determinar si un número está en una sola fila en el tiempo O (log N). Sin embargo, son las 2 direcciones las que me desvían.

Otra solución que pensé que podría funcionar es comenzar en algún punto intermedio. Si el valor medio es menor que mi objetivo, entonces puedo estar seguro de que está en el cuadrado izquierdo de la matriz desde el medio. Luego me muevo en diagonal y vuelvo a comprobar, reduciendo el tamaño del cuadrado en el que podría estar el objetivo hasta que haya afinado el número objetivo.

¿Alguien tiene buenas ideas para resolver este problema?

Matriz de ejemplo:

Ordenado de izquierda a derecha, de arriba a abajo.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

He aquí un enfoque simple:

1. Empiece en la esquina inferior izquierda.
2. Si el objetivo es menor que ese valor, debe estar por encima de nosotros, así que suba uno .
3. De lo contrario, sabemos que el objetivo no puede estar en esa columna, así que mueva uno a la derecha .
4. Ir a 2.

Para una NxMmatriz, esto se ejecuta en O(N+M). Creo que sería difícil hacerlo mejor. :)

Editar: Mucha buena discusión. Estaba hablando del caso general anterior; Claramente, si No M son pequeños, podría usar un enfoque de búsqueda binaria para hacer esto en algo cercano al tiempo logarítmico.

Aquí hay algunos detalles, para aquellos que tengan curiosidad:

Historia

Este simple algoritmo se llama búsqueda de Saddleback . Ha existido por un tiempo, y es óptimo cuando N == M. Algunas referencias:

• David Gries, La ciencia de la programación . Springer-Verlag, 1989 .
• Edsgar Dijkstra, La búsqueda de Saddleback . Nota EWD-934, 1985 .

Sin embargo, cuando N < M, la intuición sugiere que la búsqueda binaria debería ser mejor que O(N+M): Por ejemplo, cuandoN == 1 , una búsqueda binaria pura se ejecutará en tiempo logarítmico en lugar de lineal.

En el peor de los casos

Richard Bird examinó esta intuición de que la búsqueda binaria podría mejorar el algoritmo Saddleback en un artículo de 2006:

• Richard S. Bird, Mejorando la búsqueda en silla de montar : una lección de diseño de algoritmos , en Matemáticas de la construcción de programas, págs.82--89, volumen 4014, 2006 .

Usando una técnica de conversación bastante inusual, Bird nos muestra que N <= Meste problema tiene un límite inferior de Ω(N * log(M/N)). Este límite tiene sentido, ya que nos da un rendimiento lineal cuando N == My un rendimiento logarítmico cuando N == 1.

Algoritmos para matrices rectangulares

Un enfoque que utiliza una búsqueda binaria fila por fila se ve así:

1. Comience con una matriz rectangular donde N < M. Digamos que Nson filas y Mcolumnas.
2. Haga una búsqueda binaria en la fila del medio para value. Si lo encontramos, habremos terminado.
3. De lo contrario, hemos encontrado un par de números adyacentes sy g, dónde s < value < g.
4. El rectángulo de números arriba y a la izquierda de ses menor que value, por lo que podemos eliminarlo.
5. El rectángulo de abajo y a la derecha de ges mayor que value, por lo que podemos eliminarlo.
6. Vaya al paso (2) para cada uno de los dos rectángulos restantes.

En términos de complejidad en el peor de los casos, este algoritmo log(M)funciona para eliminar la mitad de las posibles soluciones y luego se llama a sí mismo de forma recursiva dos veces en dos problemas más pequeños. Tenemos que repetir una versión más pequeña de ese log(M)trabajo para cada fila, pero si la cantidad de filas es pequeña en comparación con la cantidad de columnas, entonces comenzar a ser útil eliminar todas esas columnas en tiempo logarítmico .

Esto le da al algoritmo una complejidad de la T(N,M) = log(M) + 2 * T(M/2, N/2)que Bird muestra O(N * log(M/N)).

Otro enfoque publicado por Craig Gidney describe un algoritmo similar al enfoque anterior: examina una fila a la vez utilizando un tamaño de paso de M/N. Su análisis muestra que esto también se traduce en O(N * log(M/N))rendimiento.

Comparación de rendimiento

El análisis Big-O está muy bien, pero ¿qué tan bien funcionan estos enfoques en la práctica? El siguiente cuadro examina cuatro algoritmos para matrices cada vez más "cuadradas":

(El algoritmo "ingenuo" simplemente busca en todos los elementos de la matriz. El algoritmo "recursivo" se describe anteriormente. El algoritmo "híbrido" es una implementación del algoritmo de Gidney . Para cada tamaño de matriz, el rendimiento se midió cronometrando cada algoritmo sobre un conjunto fijo de 1.000.000 de matrices generadas aleatoriamente).

Algunos puntos notables:

• Como era de esperar, los algoritmos de "búsqueda binaria" ofrecen el mejor rendimiento en matrices rectangulares y el algoritmo Saddleback funciona mejor en matrices cuadradas.
• El algoritmo Saddleback funciona peor que el algoritmo "ingenuo" para matrices 1-d, presumiblemente porque hace múltiples comparaciones en cada elemento.
• El impacto de rendimiento que adoptan los algoritmos de "búsqueda binaria" en matrices cuadradas se debe presumiblemente a la sobrecarga de ejecutar búsquedas binarias repetidas.

Resumen

El uso inteligente de la búsqueda binaria puede proporcionar O(N * log(M/N)rendimiento tanto para matrices rectangulares como cuadradas. El O(N + M)algoritmo "saddleback" es mucho más simple, pero sufre una degradación del rendimiento a medida que las matrices se vuelven cada vez más rectangulares.

Este problema lleva Θ(b lg(t))tiempo, dónde b = min(w,h)y t=b/max(w,h). Discuto la solución en esta publicación de blog .

Límite inferior

Un adversario puede obligar a un algoritmo a realizar Ω(b lg(t))consultas restringiéndose a la diagonal principal:

Leyenda: las celdas blancas son elementos más pequeños, las celdas grises son elementos más grandes, las celdas amarillas son elementos más pequeños o iguales y las celdas naranjas son elementos más grandes o iguales. El adversario obliga a que la solución sea la celda amarilla o naranja que dure el algoritmo.

Tenga en cuenta que hay blistas de tamaño ordenadas independientes t, que requieren que las Ω(b lg(t))consultas se eliminen por completo.

Algoritmo

1. (Suponga sin pérdida de generalidad que w >= h )
2. Compare el elemento de destino con la celda t a la izquierda de la esquina superior derecha del área válida
   • Si el elemento de la celda coincide, devuelve la posición actual.
   • Si el elemento de la celda es menor que el elemento de destino, elimine el resto t celdas en la fila con una búsqueda binaria. Si se encuentra un elemento coincidente al hacer esto, regrese con su posición.
   • De lo contrario, el elemento de la celda es más que el elemento de destino, eliminando tcolumnas cortas.
3. Si no queda un área válida, devuelva el error
4. Ir al paso 2

Encontrar un artículo:

Determinar que un artículo no existe:

Leyenda: las celdas blancas son elementos más pequeños, las celdas grises son elementos más grandes y la celda verde es un elemento igual.

Análisis

Hay b*tcolumnas cortas para eliminar. Hay blargas filas para eliminar. Eliminar una fila larga cuesta O(lg(t))tiempo. Eliminando tlos costos de columnas cortasO(1) tiempo.

En el peor de los casos, tendremos que eliminar cada columna y cada fila, tomando tiempo O(lg(t)*b + b*t*1/t) = O(b lg(t)) .

Tenga en cuenta que supongo que se lgsujeta a un resultado superior a 1 (es decir lg(x) = log_2(max(2,x))). Es por eso que cuando w=h, es decir t=1, obtenemos el límite esperado de O(b lg(1)) = O(b) = O(w+h).

Código

public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer<T>.Default;

    // check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    // search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        // query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        // did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        // we eliminated most of the current minimum column
        // spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

Usaría la estrategia de divide y vencerás para este problema, similar a lo que sugieres, pero los detalles son un poco diferentes.

Esta será una búsqueda recursiva en subrangos de la matriz.

En cada paso, elija un elemento en el medio del rango. Si el valor encontrado es el que busca, entonces ha terminado.

De lo contrario, si el valor encontrado es menor que el valor que está buscando, entonces sabrá que no está en el cuadrante superior ni a la izquierda de su posición actual. Por lo tanto, busque de forma recursiva los dos subrangos: todo (exclusivamente) debajo de la posición actual, y todo (exclusivamente) a la derecha que esté en la posición actual o por encima de ella.

De lo contrario (el valor encontrado es mayor que el valor que está buscando) sabrá que no está en el cuadrante de abajo y a la derecha de su posición actual. Así que busque recursivamente los dos subrangos: todo (exclusivamente) a la izquierda de la posición actual, y todo (exclusivamente) arriba de la posición actual que está en la columna actual o una columna a la derecha.

Y ba-da-bing, lo encontraste.

Tenga en cuenta que cada llamada recursiva solo se ocupa del subrango actual, no (por ejemplo) TODAS las filas por encima de la posición actual. Solo aquellos en el subrango actual.

Aquí hay un pseudocódigo para ti:

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

Las dos respuestas principales dadas hasta ahora parecen ser el O(log N)"método ZigZag" y el O(N+M)método de búsqueda binaria. Pensé en hacer algunas pruebas comparando los dos métodos con varias configuraciones. Aquí están los detalles:

La matriz es N x N cuadrados en cada prueba, con N que varía de 125 a 8000 (el mayor montón que mi JVM podría manejar). Para cada tamaño de matriz, elegí un lugar aleatorio en la matriz para poner un archivo 2. Luego puse un en 3todas partes posibles (a la derecha y debajo del 2) y luego llené el resto de la matriz con1. Algunos de los comentaristas anteriores parecían pensar que este tipo de configuración produciría el peor tiempo de ejecución para ambos algoritmos. Para cada tamaño de matriz, elegí 100 ubicaciones aleatorias diferentes para el 2 (objetivo de búsqueda) y ejecuté la prueba. Registré el tiempo de ejecución promedio y el tiempo de ejecución en el peor de los casos para cada algoritmo. Debido a que estaba sucediendo demasiado rápido para obtener buenas lecturas de ms en Java, y porque no confío en nanoTime () de Java, repetí cada prueba 1000 veces solo para agregar un factor de sesgo uniforme a todas las veces. Aquí están los resultados:

ZigZag venció al binario en cada prueba tanto para el tiempo promedio como para el peor de los casos, sin embargo, todos están dentro de un orden de magnitud entre sí más o menos.

Aquí está el código de Java:

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false; 
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

Esta es una prueba breve del límite inferior del problema.

No puede hacerlo mejor que el tiempo lineal (en términos de dimensiones de la matriz, no del número de elementos). En la siguiente matriz, cada uno de los elementos marcados como *puede ser 5 o 6 (independientemente de los demás). Entonces, si su valor objetivo es 6 (o 5), el algoritmo debe examinarlos todos.

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

Por supuesto, esto también se expande a arreglos más grandes. Esto significa que esta respuesta es óptima.

Actualización: como señaló Jeffrey L Whitledge, solo es óptimo como límite inferior asintótico en el tiempo de ejecución frente al tamaño de los datos de entrada (tratado como una sola variable). Se puede mejorar el tiempo de ejecución tratado como una función de dos variables en ambas dimensiones de la matriz.

Creo que aquí está la respuesta y funciona para cualquier tipo de matriz ordenada.

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

Interesante pregunta. Considere esta idea: cree un límite donde todos los números sean mayores que su objetivo y otro donde todos los números sean menores que su objetivo. Si queda algo entre los dos, ese es tu objetivo.

Si estoy buscando 3 en su ejemplo, leo en la primera fila hasta que llego a 4, luego busco el número adyacente más pequeño (incluidas las diagonales) mayor que 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Ahora hago lo mismo para esos números menores a 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Ahora pregunto, ¿hay algo dentro de los dos límites? Si es así, debe ser 3. Si no, entonces no hay 3. Algo indirecto ya que no encuentro el número, simplemente deduzco que debe estar allí. Esto tiene la ventaja adicional de contar TODOS los 3.

Probé esto en algunos ejemplos y parece funcionar bien.

La búsqueda binaria a través de la diagonal de la matriz es la mejor opción. Podemos averiguar si el elemento es menor o igual que los elementos de la diagonal.

A. Haga una búsqueda binaria en aquellas líneas donde podría estar el número objetivo.

B. Hágalo un gráfico: busque el número tomando siempre el nodo vecino no visitado más pequeño y retrocediendo cuando se encuentre un número demasiado grande

La búsqueda binaria sería el mejor enfoque, en mi opinión. A partir de 1/2 x, 1/2 y lo cortará por la mitad. Es decir, un cuadrado de 5x5 sería algo así como x == 2 / y == 3. Redondeé un valor hacia abajo y un valor hacia arriba para mejorar la zona en la dirección del valor objetivo.

Para mayor claridad, la siguiente iteración le daría algo como x == 1 / y == 2 O x == 3 / y == 5

Bueno, para empezar, supongamos que estamos usando un cuadrado.

1 2 3
2 3 4
3 4 5

1. Buscando un cuadrado

Usaría una búsqueda binaria en diagonal. El objetivo es localizar el número más pequeño que no sea estrictamente más bajo que el número objetivo.

Digamos que estoy buscando, por 4ejemplo, luego terminaría localizando 5en (2,2).

Entonces, tengo la seguridad de que si 4está en la mesa, está en una posición (x,2)o (2,x)con xadentro [0,2]. Bueno, son solo 2 búsquedas binarias.

La complejidad no es abrumadora: O(log(N))(3 búsquedas binarias en rangos de longitud N)

2. Buscando un rectángulo, enfoque ingenuo

Por supuesto, se vuelve un poco más complicado cuando Ny Mdifieren (con un rectángulo), considere este caso degenerado:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

Y digamos que estoy buscando 9... El enfoque diagonal sigue siendo bueno, pero la definición de diagonal cambia. Aquí está mi diagonal [1, (5 or 6), 17]. Digamos que recogí [1,5,17], entonces sé que si 9está en la tabla, está en la subparte:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

Esto nos da 2 rectángulos:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

¡Entonces podemos recurrir! probablemente comenzando por el que tiene menos elementos (aunque en este caso nos mata).

Debo señalar que si una de las dimensiones es menor que 3, no podemos aplicar los métodos diagonales y debemos usar una búsqueda binaria. Aquí significaría:

• Aplicar búsqueda binaria activada 10 11 12 13 14 15 16, no encontrada
• Aplicar búsqueda binaria activada 5 6 7 8, no encontrada
• Aplicar búsqueda binaria activada 6 7 8 9, no encontrada

Es complicado porque para obtener un buen rendimiento, es posible que desee diferenciar entre varios casos, según la forma general ...

3. Buscando un rectángulo, enfoque brutal

Sería mucho más fácil si nos ocupamos de un cuadrado ... así que vamos a arreglar las cosas.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

Ahora tenemos un cuadrado.

Por supuesto, probablemente NO crearemos esas filas, simplemente podríamos emularlas.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

por lo que se comporta como un cuadrado sin ocupar más memoria (a costa de la velocidad, probablemente, dependiendo de la caché ... bueno: p)

EDITAR:

Entendí mal la pregunta. Como señalan los comentarios, esto solo funciona en el caso más restringido.

En un lenguaje como C que almacena datos en orden de fila principal, simplemente trátelo como una matriz 1D de tamaño n * my use una búsqueda binaria.

Tengo una solución recursiva Divide & Conquer. La idea básica para un paso es: sabemos que la parte superior izquierda (LU) es la más pequeña y la parte inferior derecha (RB) es el número más grande, por lo que el No (N) dado debe: N> = LU y N <= RB

IF N == LU y N == RB :::: Elemento encontrado y Abortar devolviendo la posición / Índice Si N> = LU y N <= RB = FALSE, No no está allí y aborta. Si N> = LU y N <= RB = TRUE, divida la matriz 2D en 4 partes iguales de la matriz 2D cada una de manera lógica. Y luego aplique el mismo paso de algoritmo a las cuatro submatriz.

Mi algoritmo es correcto lo he implementado en la PC de mis amigos. Complejidad: cada 4 comparaciones se pueden usar para deducir el número total de elementos a un cuarto en el peor de los casos. Entonces, mi complejidad llega a ser 1 + 4 x lg (n) + 4 Pero realmente esperaba que esto funcionara en O (norte)

Creo que algo está mal en algún lugar de mi cálculo de Complejidad, corríjalo si es así.

La solución óptima es comenzar en la esquina superior izquierda, que tiene un valor mínimo. Muévase en diagonal hacia abajo a la derecha hasta que golpee un elemento cuyo valor> = valor del elemento dado. Si el valor del elemento es igual al del elemento dado, devuelve encontrado como verdadero.

De lo contrario, desde aquí podemos proceder de dos formas.

Estrategia 1:

1. Sube en la columna y busca el elemento dado hasta llegar al final. Si lo encuentra, devuelva encontrado como verdadero
2. Muévase a la izquierda en la fila y busque el elemento dado hasta llegar al final. Si lo encuentra, devuelva encontrado como verdadero
3. retorno encontrado como falso

Estrategia 2: Sea i el índice de fila y j el índice de columna del elemento diagonal en el que nos hemos detenido. (Aquí tenemos i = j, por cierto). Sea k = 1.

• Repita los pasos a continuación hasta que ik> = 0
  1. Busque si a [ik] [j] es igual al elemento dado. si es así, devuelva encontrado como verdadero.
  2. Busque si a [i] [jk] es igual al elemento dado. si es así, devuelva encontrado como verdadero.
  3. Incremento k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    // base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    // early fails
    // array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    // arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    // arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    // arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    // alas ! i have to keep looking

    // arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        // search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    // arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

Sugiero que almacene todos los caracteres en un archivo 2D list. luego busque el índice del elemento requerido si existe en la lista.

Si no está presente, imprima el mensaje apropiado; de lo contrario, imprima la fila y la columna como:

row = (index/total_columns) y column = (index%total_columns -1)

Esto incurrirá solo en el tiempo de búsqueda binaria en una lista.

Sugiera correcciones. :)

Si la solución O (M log (N)) está bien para una matriz MxN -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

Demostración funcional de C ++.

Por favor, avíseme si esto no funcionaría o si hay un error.

He estado haciendo esta pregunta en entrevistas durante la mayor parte de una década y creo que solo una persona ha podido encontrar un algoritmo óptimo.

Mi solución siempre ha sido:

1. Búsqueda binaria en la diagonal media, que es la diagonal que corre hacia abajo y hacia la derecha, que contiene el elemento en (rows.count/2, columns.count/2).

2. Si se encuentra el número objetivo, devuelve verdadero.

3. De lo contrario, se habrán encontrado dos números ( uy v) de manera que usea ​​más pequeño que el objetivo, vsea ​​más grande que el objetivo y vesté uno a la derecha y otro hacia abajo u.

4. Busque de forma recursiva la submatriz a la derecha uy la parte superior de vy la que está al final uy a la izquierda de v.

Creo que esta es una mejora estricta sobre el algoritmo dado por Nate aquí , ya que buscar en la diagonal a menudo permite una reducción de más de la mitad del espacio de búsqueda (si la matriz está cerca del cuadrado), mientras que buscar una fila o columna siempre resulta en una eliminación de exactamente la mitad.

Aquí está el código en (probablemente no terriblemente Swifty) Swift:

import Cocoa

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if (matrix.isEmpty || matrix[0].isEmpty) {
            return false
        }

        return _searchMatrix(matrix, 0..<matrix.count, 0..<matrix[0].count, target)
    }

    func _searchMatrix(_ matrix: [[Int]], _ rows: Range<Int>, _ columns: Range<Int>, _ target: Int) -> Bool {
        if (rows.count == 0 || columns.count == 0) {
            return false
        }
        if (rows.count == 1) {
            return _binarySearch(matrix, rows.lowerBound, columns, target, true)
        }
        if (columns.count == 1) {
            return _binarySearch(matrix, columns.lowerBound, rows, target, false)
        }

        var lowerInflection = (-1, -1)
        var upperInflection = (Int.max, Int.max)
        var currentRows = rows
        var currentColumns = columns
        while (currentRows.count > 0 && currentColumns.count > 0 && upperInflection.0 > lowerInflection.0+1) {
            let rowMidpoint = (currentRows.upperBound + currentRows.lowerBound) / 2
            let columnMidpoint = (currentColumns.upperBound + currentColumns.lowerBound) / 2
            let value = matrix[rowMidpoint][columnMidpoint]
            if (value == target) {
                return true
            }

            if (value > target) {
                upperInflection = (rowMidpoint, columnMidpoint)
                currentRows = currentRows.lowerBound..<rowMidpoint
                currentColumns = currentColumns.lowerBound..<columnMidpoint
            } else {
                lowerInflection = (rowMidpoint, columnMidpoint)
                currentRows = rowMidpoint+1..<currentRows.upperBound
                currentColumns = columnMidpoint+1..<currentColumns.upperBound
            }
        }
        if (lowerInflection.0 == -1) {
            lowerInflection = (upperInflection.0-1, upperInflection.1-1)
        } else if (upperInflection.0 == Int.max) {
            upperInflection = (lowerInflection.0+1, lowerInflection.1+1)
        }

        return _searchMatrix(matrix, rows.lowerBound..<lowerInflection.0+1, upperInflection.1..<columns.upperBound, target) || _searchMatrix(matrix, upperInflection.0..<rows.upperBound, columns.lowerBound..<lowerInflection.1+1, target)
    }

    func _binarySearch(_ matrix: [[Int]], _ rowOrColumn: Int, _ range: Range<Int>, _ target: Int, _ searchRow : Bool) -> Bool {
        if (range.isEmpty) {
            return false
        }

        let midpoint = (range.upperBound + range.lowerBound) / 2
        let value = (searchRow ? matrix[rowOrColumn][midpoint] : matrix[midpoint][rowOrColumn])
        if (value == target) {
            return true
        }

        if (value > target) {
            return _binarySearch(matrix, rowOrColumn, range.lowerBound..<midpoint, target, searchRow)
        } else {
            return _binarySearch(matrix, rowOrColumn, midpoint+1..<range.upperBound, target, searchRow)
        }
    }
}

Dada una matriz cuadrada de la siguiente manera:

[ a B C ]
[def]
[ijk]

Sabemos que a <c, d <f, i <k. Lo que no sabemos es si d <c o d> c, etc. Tenemos garantías solo en 1 dimensión.

Mirando los elementos finales (c, f, k), podemos hacer una especie de filtro: ¿N <c? buscar (): siguiente (). Por lo tanto, tenemos n iteraciones sobre las filas, y cada fila toma O (log (n)) para la búsqueda binaria u O (1) si se filtra.

Déjame dar un EJEMPLO donde N = j,

1) Compruebe la fila 1. j <c? (no, ve a continuación)

2) Compruebe la fila 2. j <f? (sí, la búsqueda de contenedores no obtiene nada)

3) Verifique la fila 3. j <k? (sí, bin search lo encuentra)

Inténtelo de nuevo con N = q,

1) Compruebe la fila 1. q <c? (no, ve a continuación)

2) Compruebe la fila 2. q <f? (no, ve a continuación)

3) Compruebe la fila 3. q <k? (no, ve a continuación)

Probablemente haya una solución mejor, pero es fácil de explicar ... :)

Como se trata de una pregunta de entrevista, parece conducir a una discusión sobre la programación paralela y Map-reduce algoritmos de .

Ver http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html