Mientras hago el segundo código kata (que le pide que implemente un algoritmo de búsqueda binaria cinco veces, cada vez con un método diferente), he encontrado una solución ligeramente diferente que funciona de la siguiente manera:
Si tengo un conjunto ordenado de longitud 100 y veo que su campo inicial contiene el número 200 y su campo final contiene el número 400, yo, como matemático que estudia a humanos, probablemente comenzaría a buscar alrededor del campo 35 si estuviera buscando el número 270, y no el campo 50 como en un algoritmo de búsqueda binaria normal.
Entonces, si el número en el campo 35 de la matriz es 270, 35 es el índice que estaba buscando.
Si ese no es el caso, puedo comparar el número que obtuve (digamos 280) y repetir la operación tomando la parte inferior de la matriz (entonces tengo 35 campos con el campo inicial que contiene 200 y el campo final que contiene 280) si el el número que encontré es mayor que el que estoy buscando, o la parte superior de la matriz (digamos que obtuve 260: ahora tengo 65 índices, el primero contiene 260 y el último contiene 400. Orientativamente, me dirigiría hacia el revés índice 4 de esta matriz secundaria, que es el índice 39 de toda la matriz) si el número que obtuve es menor que el número que estoy buscando.
La pregunta es: ¿puede este algoritmo considerarse un algoritmo de búsqueda binaria? Si no, ¿tiene su propio nombre?
fuente
Respuestas:
No llamaría a esto una búsqueda binaria.
Es claramente similar a la búsqueda binaria y es natural verlo como un refinamiento de la búsqueda binaria. Sin embargo, tiene características de complejidad de algoritmo significativamente diferentes, la búsqueda de interpolación ha esperado un tiempo de ejecución de O (log (log (n)) suponiendo que los datos se distribuyen uniformemente, sin embargo, paga esto teniendo O (n) el peor tiempo de ejecución.
Prefiero decir "El peor tiempo de ejecución de la búsqueda binaria es O (log (n))" en lugar de "Dependiendo de la elección de los elementos delimitadores, el peor tiempo de ejecución de la búsqueda binaria es O (log (n))". Esto significa que no puedo clasificar la búsqueda de interpolación como un algoritmo de búsqueda binaria.
fuente
fuente
Creo que la terminología correcta sería una búsqueda psicotómica analizada.
Usted busca en una matriz plana con una búsqueda ponderada posterior basada en la supuesta distribución plana de los números que contiene.
Esto corresponde a cómo una persona buscaría una palabra en un diccionario. Pero puede ser muy ineficiente si la distribución de datos es irregular.
fuente