algorithm search multidimensional-array

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



search multidimensional-array (19)

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

Digamos que me dieron una matriz 2d donde todos los números en 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 desaniman.

Otra solución que pensé que podría funcionar es comenzar en algún lugar en el medio. Si el valor medio es menor que mi objetivo, entonces puedo estar seguro de que está en la porción cuadrada izquierda de la matriz desde el centro. Luego me muevo en diagonal y lo 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 alguna buena idea para resolver este problema?

Ejemplo de matriz:

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

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

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

Aquí hay un enfoque simple:

  1. Comience 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, por lo tanto, mueva a la derecha .
  4. Ir a 2.

Para una matriz NxM , 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 N o M son pequeños, puede usar un enfoque de búsqueda binaria para hacer esto en algo que se aproxime al tiempo logarítmico.

Aquí hay algunos detalles, para aquellos que son curiosos:

Historia

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

Sin embargo, cuando N < M , la intuición sugiere que la búsqueda binaria debería ser mejor que O(N+M) : por ejemplo, cuando N == 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 de Saddleback en un documento de 2006:

Utilizando una técnica conversacional bastante inusual, Bird nos muestra que para N <= M , este 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 == M y el 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 N es filas y M es columnas.
  2. Haga una búsqueda binaria en la fila del medio para obtener value . Si lo encontramos, terminamos.
  3. De lo contrario, hemos encontrado un par adyacente de números s y g , donde s < value < g .
  4. El rectángulo de números arriba y a la izquierda de s es menor que el value , por lo que podemos eliminarlo.
  5. El rectángulo debajo y a la derecha de g es mayor que el value , por lo que podemos eliminarlo.
  6. Vaya al paso (2) para cada uno de los dos rectángulos restantes.

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

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

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

Comparación de rendimiento

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

(El algoritmo "ingenuo" simplemente busca cada elemento de la matriz. El algoritmo "recursivo" se describe más arriba. 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 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 de Saddleback funciona peor que el algoritmo "ingenuo" para matrices de 1-d, presumiblemente porque hace comparaciones múltiples en cada elemento.
  • El rendimiento alcanzado que los algoritmos de "búsqueda binaria" toman 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 un rendimiento O(N * log(M/N) para matrices rectangulares y cuadradas. El algoritmo O(N + M) "saddleback" es mucho más simple, pero sufre degradación del rendimiento a medida que las matrices se vuelven cada vez más rectangulares .

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 la diagonal. El objetivo es localizar el número más pequeño que no sea estrictamente inferior al número objetivo.

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

Entonces, estoy seguro de que si 4 está en la tabla, está en una posición ya sea (x,2) o (2,x) con x en [0,2] . Bueno, eso son solo 2 búsquedas binarias.

La complejidad no es desalentadora: 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 N y M difieren (con un rectángulo), considera 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í mi diagonal es [1, (5 or 6), 17] . Digamos que recogí [1,5,17] , entonces sé que si 9 está 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 en 10 11 12 13 14 15 16 , no encontrado
  • Aplicar búsqueda binaria en 5 6 7 8 , no encontrado
  • Aplicar búsqueda binaria en 6 7 8 9 , no encontrado

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

3. Buscando un rectángulo, enfoque brutal

Sería mucho más fácil si lidiáramos con un cuadrado ... así que vamos a cuadrar 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 creamos esas filas, podríamos simplemente 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 memoria caché ... oh bien: p)

Creo que esta es 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)); } }

EDITAR:

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

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

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

No puede hacerlo mejor que el tiempo lineal (en términos de dimensiones de la matriz, no de la cantidad de elementos). En el siguiente cuadro, 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 se expande a matrices más grandes también. Esto significa que esta respuesta es óptima.

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

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

Límite inferior

Un adversario puede forzar un algoritmo para hacer consultas Ω(b lg(t)) , restringiéndose a la diagonal principal:

Leyenda: los glóbulos blancos son elementos más pequeños, las celdas grises son elementos más grandes, las celdas amarillas son elementos más o menos iguales y las celdas anaranjadas son elementos más o menos iguales. El adversario obliga a la solución a ser la celda amarilla o naranja que el algoritmo consulta por última vez.

Observe que hay b listas ordenadas independientes de tamaño t , que requieren consultas Ω(b lg(t)) para eliminar por completo.

Algoritmo

  1. (Supongamos sin pérdida de generalidad que w >= h )
  2. Compare el artículo 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, devuelva la posición actual.
    • Si el elemento de la celda es menor que el elemento de destino, elimine las restantes t de 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 t columnas cortas.
  3. Si no queda área válida, falla de devolución
  4. Ir al paso 2

Encontrar un artículo:

La determinación de un artículo no existe:

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

Análisis

Hay b*t columnas cortas para eliminar. Hay b filas largas para eliminar. La eliminación de una fila larga cuesta el tiempo O(lg(t)) . La eliminación de t columnas cortas cuesta O(1) tiempo.

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

Tenga en cuenta que supongo que lg abrazaderas a un resultado superior a 1 (es decir, lg(x) = log_2(max(2,x)) ). Es por eso que cuando w=h , que significa 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; }

Hasta ahora, las dos respuestas principales parecen ser el método O(log N) "ZigZag" y el método de búsqueda binaria O(N+M) . Pensé que haría algunas pruebas para comparar los dos métodos con varias configuraciones. Aquí están los detalles:

El conjunto es N x N cuadrado en cada prueba, con N variando de 125 a 8000 (el más grande mi montón de JVM podría manejar). Para cada tamaño de matriz, elegí un lugar aleatorio en la matriz para poner un único 2 . Luego puse un 3 todas las direcciones posibles (a la derecha y debajo de las 2) y luego llené el resto de la matriz con 1 . 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 realicé la prueba. Grabé el tiempo promedio de ejecución y el peor tiempo de ejecución para cada algoritmo. Debido a que estaba sucediendo demasiado rápido para obtener buenas lecturas de ms en Java, y como no confío en el nanoTime de Java (), repetí cada prueba 1000 veces solo para agregar un factor de polarización uniforme a todas las veces. Aquí están los resultados:

ZigZag supera el binario en todas las pruebas, tanto para el promedio como para el peor de los casos, sin embargo, todos se encuentran 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"); } }

Interesante pregunta. Considera esta idea: crea un límite donde todos los números sean mayores que tu objetivo y otro donde todos los números sean menores que tu 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 toco 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 que 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. Tipo de indirecto, ya que en realidad no encuentro el número, solo deduzco que debe estar allí. Esto tiene la ventaja adicional de contar TODOS los 3.

Intenté esto con 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 en la diagonal.

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

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

La solución óptima es comenzar en la esquina superior izquierda, que tiene un valor mínimo. Mueve diagonalmente hacia la derecha hasta que toques un elemento cuyo valor> = valor del elemento dado. Si el valor del elemento es igual al del elemento dado, return encontrado como verdadero.

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

Estrategia 1:

  1. Desplácese hacia arriba en la columna y busque el elemento dado hasta que lleguemos al final. Si se encuentra, el resultado se encuentra como verdadero
  2. Muévase hacia la izquierda en la fila y busque el elemento dado hasta que lleguemos al final. Si se encuentra, el resultado se encuentra como verdadero
  3. return encontrado como falso

Estrategia 2: Deje que denote el índice de la fila y j denote el índice de la columna del elemento diagonal que hemos detenido. (Aquí tenemos i = j, BTW). Deje 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í, devuelve encontrado como verdadero.
    2. Busque si a [i] [jk] es igual al elemento dado. Si es así, devuelve 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

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 de C ++ en funcionamiento.

Please do let me know if this wouldn''t work or if there is a bug it it.

Sugiero que guarde todos los personajes en una 2D list . luego encuentre 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 solo incurrirá en el tiempo de búsqueda binario en una lista.

Por favor, sugiera cualquier corrección. :)

Tengo una solución recursiva de Divide & Conquer. La idea básica para un paso es: sabemos que la Izquierda-Superior (LU) es la más pequeña y la inferior derecha (RB) es el no. 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 Abortando devolviendo la posición / Índice Si N> = LU y N <= RB = FALSE, No no está ahí y aborta. Si N> = LU y N <= RB = TRUE, divida la matriz 2D en 4 partes iguales de la matriz 2D, cada una de forma lógica ... Y luego aplique el mismo paso de algoritmo a las cuatro suborganizaciones.

My Algo is Correct lo he implementado en la PC de mis amigos. Complejidad: cada 4 comparaciones se pueden usar para deducir el total de elementos no a un cuarto en el peor de los casos ... Entonces mi complejidad viene 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í ..

Usaría la estrategia de dividir y vencer para este problema, similar a lo que sugirió, pero los detalles son un poco diferentes.

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

En cada paso, elige un elemento en el medio del rango. Si el valor encontrado es lo que estás buscando, entonces has terminado.

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

De lo contrario, (el valor encontrado es mayor que el valor que está buscando) sabrá que no está en el cuadrante de abajo ni a la derecha de su posición actual. Así que buscar recursivamente los dos subintervalos: todo (exclusivamente) a la izquierda de la posición actual, y todo (exclusivamente) por encima 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 trata con el subrango actual solamente, 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) }

Given a square matrix as follows:

[ a b c ] [ d e f ] [ i j k ]

We know that a < c, d < f, i < k. What we don''t know is whether d < c or d > c, etc. We have guarantees only in 1-dimension.

Looking at the end elements (c,f,k), we can do a sort of filter: is N < c ? search() : next(). Thus, we have n iterations over the rows, with each row taking either O( log( n ) ) for binary search or O( 1 ) if filtered out.

Let me given an EXAMPLE where N = j,

1) Check row 1. j < c? (no, go next)

2) Check row 2. j < f? (yes, bin search gets nothing)

3) Check row 3. j < k? (yes, bin search finds it)

Try again with N = q,

1) Check row 1. q < c? (no, go next)

2) Verifique la fila 2. q <f? (no, ve después)

3) Verifique la fila 3. q <k? (no, ve después)

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

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 ; }