Elément de pic d'un tableau

def pic_lineaire(tab):
    """
    Recherche linéaire d'un élément pic
    Complexité : O(n)
    """
    n = len(tab)
    
    # Cas particuliers
    if n == 1:
        return tab[0]
    if n == 2:
        return max(tab[0], tab[1])
    
    # Recherche d'un pic à l'intérieur du tableau
    for i in range(1, n-1):
        if tab[i] > tab[i-1] and tab[i] > tab[i+1]:
            return tab[i]
    
    # Si aucun pic intérieur, le premier ou dernier élément est un pic
    if tab[0] > tab[1]:
        return tab[0]
    else:
        return tab[n-1]


tab = [1, 4, 3, 6, 7, 5]
print(f"Tableau: {tab}")
print(f"Pic trouvé (linéaire): {pic_lineaire(tab)}")

def pic_recursif(tab, debut, fin):
    """
    Recherche dichotomique récursive d'un élément pic
    Complexité : O(log n)
    """
    if debut == fin:
        return tab[debut]
    
    milieu = (debut + fin) // 2
    
    # Gestion des bords
    if milieu == 0:
        return max(tab[0], tab[1])
    if milieu == len(tab) - 1:
        return max(tab[-2], tab[-1])
    
    # Vérifier si l'élément du milieu est un pic
    if tab[milieu] > tab[milieu-1] and tab[milieu] > tab[milieu+1]:
        return tab[milieu]
    
    # Chercher dans la direction de la montée
    if tab[milieu] > tab[milieu-1]:
        # Montée vers la droite
        return pic_recursif(tab, milieu+1, fin)
    else:
        # Montée vers la gauche
        return pic_recursif(tab, debut, milieu-1)


tab = [1, 4, 3, 6, 7, 5]
print(f"Tableau: {tab}")
print(f"Pic trouvé (récursif): {pic_recursif(tab, 0, len(tab)-1)}")

def pic_iteratif(tab):
    """
    Recherche dichotomique itérative d'un élément pic
    Complexité : O(log n) temps, O(1) espace
    """
    n = len(tab)
    debut, fin = 0, n - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        
        # Vérifier si l'élément du milieu est un pic
        gauche_ok = (milieu == 0 or tab[milieu] > tab[milieu - 1])
        droite_ok = (milieu == n - 1 or tab[milieu] > tab[milieu + 1])
        
        if gauche_ok and droite_ok:
            return tab[milieu]
        
        # Chercher dans la direction de la montée
        if milieu > 0 and tab[milieu - 1] > tab[milieu]:
            fin = milieu - 1
        else:
            debut = milieu + 1
    
    return tab[debut]


tab = [1, 4, 3, 6, 7, 5]
print(f"Tableau: {tab}")
print(f"Pic trouvé (itératif): {pic_iteratif(tab)}")