#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 17:34:09 2026

@author: vincentleprince
"""

def indice(T,k):#renvoie l'indice auquel il faut insérer T[k]
                #dans T[:k] supposé trié
    if T[0] >= T[k]:
        return ...
    elif T[k-1] <= T[k]:
        return ...
    else :
        a , b =  0 , k-1 # on maintient T[k]>T[a] et T[k]<T[b]
        while b-a > 1:
            c = (b+a)//2
            if T[c] == T[k]:
                return c
            elif T[c] < T[k]:
                a = c
            elif T[c] > T[k]:
                b = c
        return b
 
#tests :
print(indice([4,1,5,0,2,3],1))  # doit renvoyer 0
print(indice([1,4,5,0,2,3],2))  # doit renvoyer 2
print(indice([1,4,5,0,2,3],3))  # doit renvoyer 0
print(indice([0,1,4,5,2,3],4))  # doit renvoyer 2
 
    
def triInsereDicho(T):
    n = len(T)
    for k in range(1,n):
        ind = indice(T,k)
        if ind != k : #si ind==k, on ne fait rien
            tmp = T[k]
            j = k-1
            while j >= ind:
                T[j+1] = T[j]
                j -= 1
            T[ind] = tmp

#test : 
T1 = [4,1,5,0,2,3]   
# attention : cette fonction ne renvoie rien
triInsereDicho(T1)
print(T1)