¿Cuáles son las diferencias entre las plantillas del algoritmo de búsqueda binaria?
En Leetcode, hay tres plantillas diferentes para la búsqueda binaria. Puedo entender la primera que recorre los elementos del arreglo y actualiza la posición del índice (pero ¿por qué en el bucle while es left <= right en lugar de left < right?); sin embargo, las siguientes dos plantillas no están claras para mí. No sé por qué ponemos el índice derecho igual a la longitud de la matriz en lugar de longitud de la matriz – 1, y por qué usamos right = mid como la búsqueda izquierda. El bucle while de la tercera plantilla usa left + 1 < right en el bucle while y pone mid = left como la búsqueda derecha y right = mid como la búsqueda izquierda. ¿Podría explicar las diferencias entre estas tres plantillas? También estoy confundido acerca de los pasos de post-procesamiento.
Plantilla 1:
def binary_Search(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# Condición de finalización: left > right
return -1
Plantilla 2:
def binarySearch(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
# Post-procesamiento:
# Condición de finalización: left == right
if left != len(nums) and nums[left] == target:
return left
return -1
Plantilla 3:
def binarySearch(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
# Post-procesamiento:
# Condición de finalización: left + 1 == right
if nums[left] == target: return left
if nums[right] == target: return right
return -1
davy.ai
La diferencia principal entre estos tres templates es la forma en que manejan la condición de terminación y el post-procesamiento del algoritmo de búsqueda binaria.
Template 1: Este template es la implementación más básica de la búsqueda binaria, donde los índices izquierdo y derecho se inicializan como 0 y len(nums) – 1, respectivamente. La condición de terminación es que left <= right, y cada iteración del bucle while reduce el espacio de búsqueda actualizando left o right en función de si el objetivo es mayor o menor que el elemento medio. El paso de post-procesamiento es directo, ya que el bucle termina solo cuando se encuentra el objetivo o left > right, lo que implica que el objetivo no está presente en el array.
Template 2: Este template es una variación del primero, donde el índice derecho se inicializa como len(nums) en lugar de len(nums) – 1. La condición de terminación es left < right en lugar de left <= right, y la diferencia principal en el bucle while es que right = mid en lugar de right = mid – 1 cuando nums[mid] > target. El paso de post-procesamiento es necesario para determinar si el objetivo está en el último índice (que no habría sido revisado por el bucle) y, si se encuentra, devolver el índice.
Template 3: Este template es otra variación que inicializa los índices izquierdo y derecho como 0 y len(nums) – 1, respectivamente, pero la condición de terminación es left + 1 < right, lo que significa que el bucle termina cuando quedan dos elementos por buscar. La diferencia principal en el bucle while es que mid = (left + right) // 2 y left = mid en lugar de right = mid – 1 cuando nums[mid] > target. El paso de post-procesamiento verifica tanto los índices izquierdo como derecho para determinar si alguno de ellos contiene el objetivo, ya que podría ser cualquiera de ellos según las condiciones del bucle.
En cuanto a por qué estos templates difieren en la forma en que manejan los índices, las condiciones de terminación y el post-procesamiento, en gran medida depende de los requisitos del problema y las preferencias del programador. Sin embargo, comprender las diferencias entre estos templates puede ayudar a los programadores a elegir el enfoque más apropiado para su problema específico.