Мы познакомились с линейным поиском, теперь настала очередь бинарного (двоичного).

В чем же он заключается?

Есть отсортированный список чисел, берем число из его середины. Если это число больше искомого, то поиск продолжаем в левой половине списка, если меньше искомого - в правой.

Продолжаем поиск, когда находим искомое число, возвращаем его индекс, иначе делаем вывод, что такого числа нет в списке.

Как утверждается в этой статье, только 10% программистов способны написать двоичный поиск.

Поэтому рекомендую сначала реализовать самим на любимом ЯП, а потом прочитать дальше и поделиться результатом.

Возвращаясь к нашей книжной полке, предположим, что все книги отсортированы по автору, слева направо. То есть вначале полки находится книга Ахматовой, а в конце - Шолохов.

Нам же надо найти книгу, автор которой Пушкин.

Берем книгу посередине полки, смотрим, кто является ее автором. С первого раза мы потерпели неудачу, и автором данной книги оказался Тютчев.

Вспоминая, что книги отсортированы по автору, мы понимаем, что правее данной книги искомой нет, следовательно, надо искать левее.

Поэтому из поиска мы исключаем правую половину полки. Теперь возьмем книгу посередине левой половины полки и посмотрим, кто ее автор. Например, Лесков.

Значит, искомая книга находится правее. Далее берем книгу посреди оставшейся части полки. Если это та книга, которую мы искали, то все шикарно, иначе снова исключаем половину (левую или правую, в зависимости от автора) и тд.

В итоге мы либо находим искомую книгу, либо добираемся до такой малой части полки, где не будет ни одной книги. Тогда можем с увереностью сказать, что искомой книги на полке нет.

Скажу сразу, я нигде не нашел стандартного условия, описывающего ситуацию с дубликатами на полке. Поэтому будем считать, что дублей у нас не будет, но если и будут, то будем возвращать первый найденный индекс.

Процедура будет принимать те же входные параметры, что и в линейном поиске:

def binary_search(lst, x):
	lst.sort()
	pass

Здесь мы на всякий случай сортируем список.

p и r - наши первые границы. q - середина рассматриваемого “подсписка”, среднее значение суммы p и r, без дробной части.

def binary_search(lst, x):
	lst.sort()
	p = 0
	r = len(lst) - 1
	answer = None
	while p <= r:
		q = (p + r) // 2
		if lst[q] == x:
			answer = q
			break
		elif lst[q] > x:
			r = q - 1
		elif lst[q] < x:
			p = q + 1
	
	return answer

if __name__ == '__main__':
	print('='*10, binary_search([0, 1, 2, 3, 4], 2), sep='\n')

Искомый элемент найден, если значение середины “подсписка” lst[q] равно x.

Если lst[q] > x, мы исключаем все элементы справа от q.

Если lst[q] < x, мы исключаем все элементы слева до q.

Программисты допускают ошибки в следующих ситуациях:

• Есть повторяющиеся элементы.
• Список либо пуст, либо содержит 1 элемент, либо 2.
• Искомое число находится в начале или в конце списка.
• Искомого числа нет в списке.

Поэтому напишем тесты, которые желательно всегда писать в самом начале. Если я что-то забыл или пропустил - пишите, исправлю.

class TestBinarySearch(unittest.TestCase):

	def testDuplicateElements(self):
		'''
		Точно не знаю, должна ли функция возвращать результат 0 или 1. В данный ситуации вернет 1, 
		но можно дописать в коде условие, чтобы проверяло, не является ли элемент слева таким же и тд. 
		И тогда вернуть крайний левый похожий элемент.
		'''
		self.assertEqual(binary_search([1, 1, 2, 2, 3, 3, 4], 1), 1, 'Problem with duplicate elements')

	def testListLen(self):
		self.assertEqual(binary_search([], 1), None, 'Problem with empty list')
		self.assertEqual(binary_search([5], 5), 0, 'Problem with one element in list')
		self.assertEqual(binary_search([5, 6], 6), 1, 'Problem with 2 elements in list')

	def testFirstLastElements(self):
		self.assertEqual(binary_search([0, 1, 2, 3, 4, 5], 0), 0, 'Problem with first element in the list')
		self.assertEqual(binary_search([0, 1, 2, 3, 4, 5], 5), 5, 'Problem with last element in the list')

	def testNotIn(self):
		self.assertEqual(binary_search([1, 2], 3), None, 'Element not in list')

Код по-прежнему можно найти здесь.