## EXO 1
def find_closest_seq(liste, n):
    diff = None
    resultat = None
    for element in liste:
        if not diff or abs(element - n) < diff:
            diff = abs(element - n)
            resultat = element
    return resultat

l = [1, 2, 5, 8, 12, 16, 24, 56, 58, 63]
print(find_closest_seq(l, 41))

## EXO 2
# Binary search
def find_closest_bin(liste, n):
    resultat = None
    min = 0
    max = len(liste)
    found = False
    while min <= max and not found:
        mid = (max + min) // 2
        if n > liste[mid]:
            min = mid + 1
        elif n < liste[mid]:
            max = mid -1
        else:
            found = True
    if found:
        return n
    if liste[mid] < n:
        if mid == len(liste) - 1:
            return liste[mid]
        else:
            return liste[mid] if (n - liste[mid]) < (liste[mid + 1] -n) else liste[mid + 1]
    else:
        if mid == 0:
            return liste[mid]
        else:
            return liste[mid] if (liste[mid] - n) < (n - liste[mid - 1]) else liste[mid - 1]


l = [1, 2, 5, 8, 12, 16, 24, 56, 58, 63]
print(find_closest_bin(l, 41))


## EXO 3
def search_in_matrix(matrix, number):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j]==number:
                return (i,j)
    return (-1,-1)

print(search_in_matrix([[1,2,3,4],[4,5,7,8],[5,6,8,10],[6,7,9,11]], 9)) ##(3,2)

def search_in_matrix_better(matrix, number):
    i=0
    j=len(matrix)-1
    while((i<len(matrix) or matrix[i][j]>number) and (j>0 or matrix[i][j]<number)):
        if matrix[i][j]==number:
            return (i,j)
        elif matrix[i][j]<number:
            i=i+1
        else:
            j=j-1
    if matrix[i][j]==number:
        return (i,j)
    else:
        return (-1,-1)
print(search_in_matrix_better([[1,2,3,4],[4,5,7,8],[5,6,8,10],[6,7,9,11]], 5)) ##(3,2)

## EXO 4
Solution: array List pour la complexité plus faible pour l'opération GET utilisée au quotidien.

## EXO 5
Solution: l’arbre 5 est un arbre binaire de hauteur 4


## EXO 6
			10	
		/		\		
	6				18
  /	  \			 /		\
4		8		15		21			


## EXO 7
randoms = [1231321,3213125,3284016,4729273,5492710]
search = 3284016

def linear_search(randoms, search):
    for index, e in enumerate(randoms):
        if e == search:
            return index
    return -1

print (linear_search(randoms, search)) #2


## EXO 8
def binary_search(randoms, search):

    first = 0
    last = len(randoms)-1

    while first<=last:
       mid = int((first+last)/2)

       print (mid, first, last)
       if randoms[mid] == search:
           return mid
       else:
            if randoms[mid] > search:
                last -= 1
            else:
                first += 1

    return False

randoms = [1231321,3213125,3284016,4729273,5492710]
search = 4729273
print (binary_search(randoms, search))


## EXO 9
# Merge array b into array a given that array a contains len(b) extra space at

a = [33, 44, 55, 66, 88, 99, None, None, None]
b = [11, 22, 77]

j = 0
i = 0

while i < len(b):

    while j < len(a):

        if b[i] < a[j]:

            a.pop()

            a.insert(j, b[i])

            break

        else:

            j += 1

    i += 1
print(a)


## EXO 10
def peaks_valleys(listl):

    if len(listl) < 3:

        return

    for ix in range(len(listl) - 1):

        if ix % 2:

            if listl[ix] < listl[ix + 1]:

                listl[ix], listl[ix + 1] = listl[ix + 1], listl[ix]
        # Otherwise, if this is a valley:
        else:

            if listl[ix] > listl[ix + 1]:

                listl[ix], listl[ix + 1] = listl[ix + 1], listl[ix]

    print(listl)


a = [5,3,1,2,3]

peaks_valleys(a)