Структуры и алгоритмы данных Python: бинарный поиск

Поиск и сортировка Python: упражнение 1 с решением

Напишите программу на Python для бинарного поиска.
Бинарный поиск: В компьютерных науках алгоритм бинарного поиска или полуинтервального поиска находит позицию целевого значения в отсортированном массиве. Алгоритм двоичного поиска может быть классифицирован как алгоритм поиска типа «разделяй и властвуй» и выполняется в логарифмическом времени.

Пошаговый пример:

Пример решения :

Код Python:

def binary_search(item_list,item):
	first = 0
	last = len(item_list)-1
	found = False
	while( first<=last and not found):
		mid = (first + last)//2
		if item_list[mid] == item :
			found = True
		else:
			if item < item_list[mid]:
				last = mid - 1
			else:
				first = mid + 1	
	return found
	
print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))

Пример вывода:

 Ложь                                                                                                         
Правда

Блок - схема:

Визуализируйте выполнение кода Python:

Следующий инструмент визуализирует, что компьютер делает шаг за шагом при выполнении указанной программы:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущий: Python Поиск и сортировка упражнений дома.
Далее: Написать программу на Python для последовательного поиска.