Busca binária, Ordenação com bubble sort e Ordenação com insertion sort

''' https://www.coursera.org/learn/ciencia-computacao-python-conceitos-2/programming/SqdCQ/lista-de-exercicios-5
Exercício 1: Busca binária
Implemente a função busca(lista, elemento), que busca um determinado elemento em uma lista e devolve o índice correspondente à posição do elemento encontrado. Utilize o algoritmo de busca binária. Nos casos em que o elemento buscado não existir na lista, a função deve devolver o booleano False.
Além de devolver o índice correspondente à posição do elemento encontrado, sua função deve imprimir cada um dos índices testados pelo algoritmo.'''
def busca(lista, elemento):
    p, u = 0, len(lista)-1
    while p <= u:
        m = (p + u)//2
        print(m)
        if lista[m] == elemento:
            return m
        else:
            if lista[m] > elemento:
                u = m -1
            else:
                p = m + 1
    return False
def testBu():
    print("\n", busca(['a', 'e', 'i'], 'e'))# 1, 1
    print("\n", busca([1, 2, 3, 4, 5], 6))# 234, False
    print("\n", busca([1, 2, 3, 4, 5, 6], 4))# 234, 3
#testBu()
''' Exercício 2: Ordenação com bubble sort
Implemente a função bubble_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo bubble sort.
Além de devolver uma lista ordenada, ao longo do processamento sua função deve imprimir o estado atual da lista toda vez que fizer uma alteração em seus elementos.
bubble_sort([5, 1, 4, 2])
[1, 5, 4, 2]
[1, 4, 5, 2]
[1, 4, 2, 5]
[1, 2, 4, 5]
# deve devolver [1, 2, 4, 5]'''
def bubble_sort(lista):
    for i in range(len(lista)-1, 0, -1):
        for j in range(i):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
                print(lista)   
    return lista
def testBc():
    print("Return:", bubble_sort([5, 1, 4, 2]))
    '''print
    [1, 5, 4, 2]
    [1, 4, 5, 2]
    [1, 4, 2, 5]
    [1, 2, 4, 5]
    # Return: [1, 2, 4, 5]'''
#testBc()
''' Exercicio opcional. Ordenação com insertion sort
Implemente a função insertion_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo insertion sort. '''
def insertion_sort(lista):
    n = len(lista)
    for j in range(1, n):
        k = lista[j]
        i = j - 1
        while i >= 0 and lista[i] > k:
            lista[i + 1] = lista[i]
            i -= 1
        lista[i + 1] = k
    return lista
def testIns():
    print(insertion_sort([5, 1, 4, 2]))
#testIns()

#-------------------------------------------------------

def intest( lista ):
  for i in range( 1, len( lista ) ):
    chave = lista[i]
    #k = i
    while i > 0 and chave < lista[i - 1]:
        lista[i] = lista[i - 1]
        i -= 1
    lista[i] = chave
  return lista
print(intest([7, -1, 4, -7, 2, 3, -9, 5, 1, 8]))