BinarySearch
Este es un algoritmo de búsqueda para arrays ordenados
Si en el array hay números repetidos, no se asegura que se devuelva la primera ocurrencia (eso se tendría que implementar a parte) pero se asegura que se devolverá una posición donde se encuentre el número buscado.
La posición devuelta dependerá del tamaño del array y de la implementación del algoritmo
Pasos
- Seleccionamos el elemento central del array
- Si el elemento buscado es el que acabamos de seleccionar, lo hemos hallado, el algoritmo termina
- Si el número buscado es menor que el central, haremos una llamada recursiva con la parte izquierda del array. Si es mayor, lo haremos con la derecha
Repetiremos estos pasos hasta hallar el número o hasta que las varaibles y se hayan cruzado. Es este último caso, contendrá el índice del número menor más próximo, e contendrá el íncide del número mayor más próximo
from random import randint
# Warning 1: The array must be sorted
# Warning 2: If array contains repeated elements, the function will not always return the same index, but it will always return an index where the element is found
def binSearch(arr, x, i, j):
# Base case
if len(arr) == 0:
return -1
# Recursive case
else:
# If the array has only one element
if i == j:
# If the element is found
if arr[i] == x:
return i
# If the element is not found
else:
return -1
# If the array has more than one element
else:
m = (i + j) // 2
# If the element is found in the middle
if arr[m] == x:
return m
# If the element is in the left half
elif arr[m] > x:
return binSearch(arr, x, i, m-1)
# If the element is in the right half
else:
return binSearch(arr, x, m+1, j)
if __name__ == "__main__":
n = 1000
# Generate a random sorted array
arr = [randint(0, 100) for _ in range(n)]
arr.sort()
target = arr[4] # Choose an arbitrary element to search (the fifth element in the array in this example)
res1 = binSearch(arr, target, 0, len(arr)-1)
print(res1)