# Бинарный поиск
# Этот алгорит работает только с отсортированными массивами

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high)//2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

# print(binary_search([1,3,5,7,9,10,14,16,18], 16))

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# Поиск наименьшего элемента массива
def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

# Сортировка выбором
def selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))
    return new_arr

# print(selection_sort([5,3,6,4,7,1,3,2]))

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# Быстрый поиск
def quick_sort(arr):
    if len(arr) < 2:
        print(f'Return: {arr}')
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        print(f'Pivot: {pivot}')
        print(f'Less: {less}')
        print(f'Greater: {greater}')
        return quick_sort(less) + [pivot] + quick_sort(greater)
    

# print(quick_sort([5,3,6,4,7,1,3,2]))

def arr_test(arr):
    return [i for i in arr[1:]]

# print(arr_test([5,3,6,4,7,1,3,2]))

# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# Треугольник паскаля

def triangle_pascale(n):
    tr = []
    for i in range (n + 1):
        tr.append([1] + [0]*n)

    for i in range(1, n + 1):
        for j in range(1, i + 1):
            tr[i][j] = tr[i-1][j] + tr[i-1][j-1]

    for i in range(0, n + 1):
        for j in range(0, i + 1):
            print(tr[i][j], end=' ')
        print()

triangle_pascale(10)