¿Cómo debo usar la búsqueda binaria para encontrar si hay una distancia entre los números vecinos más grandes que N en una matriz ordenada? Por ejemplo:
Input: 2 5 8 11 16
Distance: 4
Entonces deberíamos obtener respuesta de que hay tal distancia entre vecinos. (entre 11 y 16)
EDITAR: Permítame ser más claro por qué quiero hacer esto con la búsqueda binaria.
Supongamos que la matriz de ENTRADA viene sin clasificar. Ex:
Input: 11 8 2 16 5
Entonces deberías ordenar la matriz para ver cuales son los vecinos. Entonces, después de que tengamos una lista ordenada, ¿no es la mejor manera de encontrar la distancia con alguna mutación de búsqueda binaria?
Respuestas
0 para la respuesta № 1No puede utilizar la búsqueda binaria en el peor de los casos, cuando todos los números están espaciados por igual en N.
La idea de una búsqueda binaria y otros algoritmos de dividir y conquistar es que se elimina aproximadamente la mitad del rango restante en cada paso. Cuando todos los elementos están espaciados en N, cada rango de tres o más elementos consecutivos podría contener un par de vecinos con la distancia de > N, por lo que no puede eliminar ninguno de los dos sub-rangos en consideración. Eventualmente examinará cada par de artículos consecutivos, lo que le costará O(NumItems).
Dicho esto, probablemente pueda optimizar un caso general para hacerlo considerablemente mejor que O(NumItems) Debido a posibles oportunidades de poda.
0 para la respuesta № 2
Usted (bueno, yo) no lo haría: la búsqueda binaria requiere una lista ordenada, y pasará más tiempo clasificando esta lista (de pares de elementos vecinos, ordenados por su distancia) de lo que simplemente escanearía la lista.