Answer the question
In order to leave comments, you need to log in
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("Элемент не найден.")
if guess > search_item:
high = middle - 1
else:
low = middle + 1
Answer the question
In order to leave comments, you need to log in
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]
и т.п.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question