fds

import random

def BinSearch(li, x):
    t = 0
    if1 = 0
    else1 = 0
    i = 0
    j = len(li)-1
    m = int(j/2)
    while li[m] != x and i < j:
        t += 1
        if x > li[m]:
            if1 += 1
            i = m+1
        else:
            else1 += 1
            j = m-1
        m = int((i+j)/2)
    if i > j:
        print(t)
        print(if1)
        print(else1)
        return 'Не найдено'
    else:
        print(t)
        print(if1)
        print(else1)
        return m

def quicksort(nums):
   if len(nums) <= 1:
       return nums
   else:
       q = random.choice(nums)
       s_nums = []
       m_nums = []
       e_nums = []
       for n in nums:
           if n < q:
               s_nums.append(n)
           elif n > q:
               m_nums.append(n)
           else:
               e_nums.append(n)
       return quicksort(s_nums) + e_nums + quicksort(m_nums)

arr = [random.randint(0, 10000) for i in range(1000000)]


arr = quicksort(arr)

print(BinSearch(arr, 55))