¿Cómo derivar la fórmula de tiempos de búsqueda binaria en lenguaje C?

Realizar una búsqueda binaria en una matriz ordenada con n elementos. El número de comparaciones a analizar se puede analizar dibujando un árbol de decisión binario. La altura del árbol de decisión binaria es el nivel [log2(n)]+1, que es el número máximo de comparaciones para la búsqueda binaria. Por ejemplo: n=1000, entonces el número máximo de comparaciones es [log2(1000)]+. 1=9+1= 10 veces.

Si desea calcular el número promedio de comparaciones, debe analizar cada nodo en el árbol de decisión binario. Habrá una comparación en el primer nivel, dos comparaciones en el segundo nivel y dos comparaciones. en el tercer nivel, compare 3 veces, y así sucesivamente ... El número de comparaciones de cada nodo se acumula y el número de nodos (número de elementos) es el número promedio de comparaciones. realizado con igual probabilidad.

Por ejemplo: una matriz ordenada con 9 elementos, y cada elemento está numerado 1, 2, 3...8, 9, el árbol de decisión binario es el siguiente:

Como Como se puede ver en la figura, si el elemento que está buscando está en la quinta posición, puede encontrarlo con solo una comparación. Si está buscando el noveno elemento, necesita 4 comparaciones. El algoritmo compara el quinto elemento respectivamente. ,7,8,9 y otros 4 elementos. Por tanto, el número medio de comparaciones es aproximadamente el siguiente:

¿Puedes entender este análisis? ¡Espero que esto ayude!