¿Por qué algunos códigos en la Búsqueda Binaria establecen el pivote medio como ‘izquierda + (derecha – izquierda) // 2’?
Por ejemplo, búsqueda binaria básica en Python:
left, right = 0, len(nums) - 1
while left <= right:
# // 2 -> piso
pivot = izquierda + (derecha - izquierda) // 2
if nums[pivot] == objetivo:
devolver pivote
if objetivo < nums[pivot]:
derecho = pivote - 1
else:
izquierda = pivote + 1
En este código, pivot es izquierda + (derecha - izquierda) // 2, no len(nums) // 2.
¿Podría explicar por qué?
davy.ai
La razón por la que se calcula el “pivote” como “izquierda + (derecha – izquierda) // 2” en lugar de simplemente “len(nums) // 2”, es evitar problemas de desbordamiento de enteros cuando la longitud de la lista de entrada es extremadamente grande.
“Len(nums) // 2” es una expresión más simple, pero implica calcular la longitud de la lista, lo que puede ser enorme y causar desbordamiento de enteros. En cambio, “izquierda + (derecha – izquierda) // 2” calcula directamente el punto medio desde los límites del índice izquierdo y derecho, lo que evita el problema de desbordamiento.
Además, calcular el punto medio de esta manera es más eficiente en términos de complejidad temporal, ya que solo implica algunas operaciones aritméticas básicas, mientras que calcular la longitud de la lista requiere iterar sobre toda la lista. La complejidad temporal del algoritmo de búsqueda binaria se vería afectada si se utilizara un enfoque de cálculo de punto medio menos eficiente.