# -*- coding:utf-8 -*-

__projet__ = "CoursS5"
__nom_fichier__ = "6_insertion"
__author__ = "Anne-Julie Tinet"
__date__ = "novembre 2022"

"""
========================================================================================================================

                                         Ex. 6 - INSERTION DANS UNE LISTE TRIEE

========================================================================================================================
"""

# Définition de fonctions
def recherche_sequentielle(liste, nb):
    """
    :param liste: liste triée par ordre croissant
    :param nb: nombre que l'on veut insérer
    :return: Indice où le nombre doit être insérer
    """
    # Recherche séquentielle
    for i in range(len(liste)):
        if liste[i] > nb:
            return i

    return len(liste)

def recherche_dichotomique(liste, nb):
    """
    :param liste: liste triée par ordre croissant
    :param nb: nombre que l'on veut insérer
    :return: Indice où le nombre doit être insérer
    """
    # On gère le cas en début de liste
    if nb < liste[0]:
        return 0

    # On gère le cas en fin de liste
    if nb > liste[-1]:
        return len(liste)

    # Intervalle de recherche initial
    mini, maxi = 0, len(liste)-1

    # On divise par 2 l'intervalle de recherche à chaque étape
    while maxi-mini > 1:

        milieu = (maxi+mini)//2

        if nb >= liste[milieu]:
            mini = milieu
        else:
            maxi = milieu

    return maxi

# Programme principal
if __name__ == '__main__':

    l = [0,2,4,6,8]

    # Validation de la recherche séquentielle
    print(recherche_sequentielle(l,-1)) #0
    print(recherche_sequentielle(l,1)) #1
    print(recherche_sequentielle(l,7)) #4
    print(recherche_sequentielle(l,9)) #5
    print(recherche_sequentielle(l,4))

    # Validation de la recherche dichotomique
    print(recherche_dichotomique(l,-1)) #0
    print(recherche_dichotomique(l,1)) #1
    print(recherche_dichotomique(l,7)) #4
    print(recherche_dichotomique(l,9)) #5
    print(recherche_dichotomique(l,4))

    # Insertion dans la liste (modification de la liste)
    l.insert(recherche_dichotomique(l,7),7)
    print(l)