"""
Proyecto 6 Busqueda Binaria
27/08/2025
Edito AHR
"""
import random
import time


def busqueda_ingenua(lista, objetivo):
    for i in range(len(lista)):  # range(len(lista)) -> 0, 1, 2, 3, ...., len(lista)-1
        if lista[i] == objetivo:
            return i
    return -1


lista = [1, 3, 5, 10, 12]
print(busqueda_ingenua(lista, 10))  # Este elemento está en la lista
print(busqueda_ingenua(lista, 15))  # Este elemento no está en la lista


#  Esta funcion requiere que los elementos de la lista esten ordenados en forma ascendente.
#  Si esta ordenados en forma descentente se harian ajustes en la logica de busqueda.
def busqueda_binaria(lista, objetivo, limite_inferior=None, limite_superior=None):
    if limite_inferior is None:  # Si no se proporciona un limite_inferior, se establece en 0
        limite_inferior = 0  # Inicio de la lista
    if limite_superior is None:  # Si no se proporciona un limite_superior, se establece en len(lista) - 1
        limite_superior = len(lista) - 1  # Final de la lista
    
    if limite_superior < limite_inferior:  # Caso base: el objetivo no está en la lista
        return -1
    
    # [1, 3, 5, 10, 12]
    #  0  1  2   3   4
    # punto_medio = (0 + 4) // 2 = 4 // 2 = 2    
    punto_medio = (limite_inferior + limite_superior) // 2  # Encuentra el punto medio de la lista
    
    if lista[punto_medio] == objetivo:  # Caso base: el objetivo está en el punto medio
        return punto_medio
    elif objetivo < lista[punto_medio]:
        return busqueda_binaria(lista, objetivo, limite_inferior, punto_medio - 1)  # Busca en la mitad izquierda
    else:
        return busqueda_binaria(lista, objetivo, punto_medio + 1, limite_superior)  # Busca en la mitad derecha


if __name__ == "__main__":
    mi_lista = [1, 3, 5, 10, 12]
    print(busqueda_binaria(mi_lista, 5))  # Debe retornar 2
    print(busqueda_binaria(mi_lista, 11))  # Debe retornar -1
    
    # Crear una lista ordenada con 10000 números aleatorios
    tamaño = 10000
    conjunto_inicial = set()  # Un conjunto no permite elementos repetidos
    
    while len(conjunto_inicial) < tamaño:
        conjunto_inicial.add(random.randint(-3*tamaño, 3*tamaño))

    lista_ordenada = sorted(list(conjunto_inicial))  # sorted() retorna una nueva lista ordenada
    
    # Medir el tiempo de busqueda ingenua
    inicio = time.time()
    for objetivo in lista_ordenada:
        busqueda_ingenua(lista_ordenada, objetivo)
    fin = time.time()
    print(f"Tiempo de busqueda ingenua: {fin - inicio} segundos")

    # Medir el tiempo de busqueda binaria
    inicio = time.time()
    for objetivo in lista_ordenada:
        busqueda_binaria(lista_ordenada, objetivo)
    fin = time.time()
    print(f"Tiempo de busqueda binaria: {fin - inicio} segundos")