import random  #Імпортуємо рандом
D = [random.randint(-10, 10) for j in range(int(input('Введіть розмір масиву: ')))]  #Потім за допомогою randint
# вирішуємо від якого числа по яке можуть бути в нашому масиві. І в кінці вводимо розмір нашого масиву
x = int(input('Введіть шуканий елемент: '))  #вводимо елемент, який ми хочемо знайти
print(D)  #виводимо наш масив на екран

D = sorted(D)  #відсортовуємо наш масив
print(D)  #виводимо на екран наш відсортований масив

l = 0  #найменший індекс
r = len(D) - 1  #найбільший індекс
k = 0  #середина нашого масиву D
flag = False
while l <= r and not flag:  #проходимо наш масив і виконуємо порівняння, але дії будуть виконуватися лише тоді,
    #коли найменший індекс буде менший за найбільший індекс або рівний йому, і not flag позначає чи знайшли ми елемент
    k = (l + r) // 2  #знаходження середини
    if D[k] == x:  #якщо D[k] дорівнює нашому шуканому елементові, ми замінюємо not flag(False) на True
        #  і тоді not flag не спрацює
        flag = True  #заміна False на True
    elif (D[k] < x):  #якщо елемент менший за шуканий, то елемент знаходиться праворуч і ми посуваємо ліву межу
        l = k + 1
    else:  #якщо елемент більший за шуканий, то елемент знаходиться ліворуч і ми посуваємо праву межу
        r = k - 1
if not flag:  #якщо flag не змінився, то елемент не знайдено
    print('Елемент не знайдений')  #і тоді виводимо 'Елемент не знайдений'
    print(f'Всього було проведено {k} порівнянь')  #Кількість порівнянь
else:  #в іншому випадку елемент був знайденик на позиції k
    print(f'Елемент {x} знайдений на позиції {k}')  #і тоді виводимо 'Елемент {x} знайдений на позиції {k}'
    print(f'Всього було проведено {k} порівнянь')  #Кількість порівнянь

