Recherche binaire en Python

from typing import List


def binary_search_loop(data: List[int], target: int) -> int:
    left, right = 0, len(data)

    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return None


if __name__ == "__main__":
    data: List[int] = [int(x) for x in input("Tableau trié(Espace délimité)Entrer: ").split()] #J'ai utilisé la notation d'inclusion
    target = int(input("Entrez la cible: "))

    result = binary_search_loop(data, target)
    if result is not None:
        print(f"found: {result}Était deuxième")
    else:
        print("not found")

from typing import List


def binary_search_recursion(data: List[int], target: int) -> int:
    def recursion(left=0, right=len(data) - 1):
        if left > right:
            return None

        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            return recursion(mid + 1, right)
        else:
            return recursion(left, mid - 1)

    return recursion()


if __name__ == "__main__":
    data: List[int] = list(map(int, input("Tableau trié(Espace délimité)Entrer: ").split())) #Utilisation de la carte
    target = int(input("Entrez la cible: "))

    result = binary_search_recursion(data, target)
    if result is not None:
        print(f"found: {result}Était deuxième")
    else:
        print("not found")

Recommended Posts