Как подсчитать количество операций в бинарном поиске(Python)

Question

def binary_search(key,start,stop):
    if(start<=stop):
        mid=int((start+stop)/2)
        if list[mid]==key:
            return mid
        elif list[mid]<key:
            mid=binary_search(key,mid+1,stop)
            return mid
        else:
            mid=binary_search(key,start,mid-1)
            return mid
    else:
        return -1


list = [7, 13, 17, 27, 33, 37, 40, 41, 44, 59, 60, 65, 67, 69, 84,89]  

key = int(input('Введіть ключ: '))

start=0
stop = len(list)-1

mid=binary_search(key,start,stop)

if mid != -1:
    print("Елемент знайдено")
else:
    print("Елемент не знайдено")

Answer 1

Добавьте переменную со счётчиком, передавайте её в функцию и увеличивайте там, ну и на возврате из функции её подхватывайте обратно:

def binary_search(key,start,stop,count):
    count += 1
    if(start<=stop):
        mid=int((start+stop)/2)
        if list[mid]==key:
            return mid, count
        elif list[mid]<key:
            mid,count=binary_search(key,mid+1,stop,count)
            return mid, count
        else:
            mid,count=binary_search(key,start,mid-1,count)
            return mid, count
    else:
        return -1, count


list = [7, 13, 17, 27, 33, 37, 40, 41, 44, 59, 60, 65, 67, 69, 84,89]  

key = int(input('Введіть ключ: '))

start=0
stop = len(list)-1

mid,count=binary_search(key,start,stop,0)

if mid != -1:
    print("Елемент знайдено", count)
else:
    print("Елемент не знайдено", count)

БЛОГ НА HUSL

Как подсчитать количество операций в бинарном поиске(Python)

Ответы (1 шт):