H
H
hlystik2021-11-10 17:00:30
Python
hlystik, 2021-11-10 17:00:30

Can someone explain in simple terms how these lines of code work?

Here is the complete code.

def binary_search(lst, search_item):
    low = 0
    high = len(lst) - 1
    search_res = False

    while low <= high and not search_res:
        middle = (low + high) // 2
        guess = lst[middle]

        if guess == search_item:
            search_res = True

        if guess > search_item:
            high = middle - 1

        else:
            low = middle + 1
    return search_res

lst = [1,3,6,5,70,6,6,7]
lst = sorted(lst)
print(lst)

value = 20
result = binary_search(lst, value)
if result:
    print("Элемент найден!")
    print(value)
else:
    print("Элемент не найден.")

Simply put, I do not understand how this particular part of the code works.
if guess > search_item:
            high = middle - 1

        else:
            low = middle + 1


I apologize for such a stupid question, I just reached a dead end from which I can not get out for like two days.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Vladimir Kuts, 2021-11-10
@hlystik

1. Sort the list
2. Take the element in the middle of the list
3. Compare with the desired
4. If the desired is equal to the element - cheers - found
5. If the desired is greater than the element, then there is no point in looking to the left of the element - the numbers are obviously smaller there - we take the part of the list to the right of element - from position +1 to end
6. If the desired is less than the element, then there is no point in looking to the right of the element - the numbers are obviously large there - we take the part of the list to the left of the element - from the beginning and to position -1 to element
7. Repeat the procedure with step 2 with the new part of the list.

[1, 3, 5, 6, 6, 6, 7, 70] 
 0, 1, 2, 3, 4, 5, 6, 7   # позиции элементов
элемент посредине - это 6 на позиции 3.

Сравниваем с 20. 20 больше 6

Значит слева от 6-ки смотреть числа смысла нет - это числа [1, 3, 5].

Сама 6 тоже не нужна - мы ее уже сравнили с искомым и уже узнали что это не то число.

Значит берем часть списка справа - 
с позиции +1 - то есть с 4-й позиции и до конца - [6, 6, 7, 70]

и т.п.

Is it clear now?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question