¿Qué es la dicotomía?
El método de bisección es el método de dividir en dos. Sea [a, b] el intervalo cerrado de R. El método de bisección sucesiva consiste en crear la siguiente secuencia de intervalos ([an, bn]): a0 =a, b0=b, y para cualquier número natural n, [an+1, bn+1] es igual a [an, cn] o igual a [cn, bn], donde cn representa [an, bn] punto medio. Información ampliada
Algoritmo típico
Algoritmo: Este método es adecuado cuando la cantidad de datos es grande. Cuando se utiliza la búsqueda binaria, los datos deben ordenarse.
Idea básica: suponga que los datos están ordenados en orden ascendente. Para una clave de valor determinada, la comparación comienza desde la posición media k de la secuencia.
Si la posición actual es arr. El valor [k] es igual a key, la búsqueda es exitosa;
Si key es menor que el valor de la posición actual arr[k], busca en la primera mitad de la secuencia, arr[low, mid- 1];
Si la clave es mayor que el valor de la posición actual arr[k], continúe buscando arr[mid+1,high] en la segunda mitad de la secuencia,
hasta que se encuentre, complejidad del tiempo: O(log(n)) .
Referencia: Dicotomía (un término en el campo de las matemáticas) Enciclopedia Baidu