¿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