Основой изучения информатики является анализ алгоритмов и структур данных. Это может звучать пугающе и вызывать образы гениев-математиков, выписывающих на доске эзотерические символы, но я могу заверить, что это не так.
Алгоритм — это просто последовательность шагов, которые всегда заканчиваются желаемым результатом. Бинарный поиск — это один из алгоритмов, которым учат новичков, потому что он помогает понять истинную красоту информатики. Двоичный поиск — это сокращение времени, необходимого для поиска фрагмента данных. Для небольших наборов данных время может быть несерьезным фактором, но когда вам нужно искать наборы данных с тысячами или миллионами элементов, выбор, эффективный с точки зрения времени, может быть разницей между успехом и неудачей.
Вот пример бинарного поиска. Скажем, у вас есть отсортированный список чисел: [10,30,50,99,100,150,600]. И вы хотите найти позицию числа «150». Что ж, вы могли бы сделать это, проходя одно за другим через весь список чисел, но если бы этот список состоял из 1 000 000 элементов, вы бы делали это очень долго. Мы можем сэкономить много времени, выполнив следующие шаги:
- Найдите среднюю позицию в списке, взяв среднее значение самой низкой позиции и самой высокой позиции. Округлите в меньшую сторону, чтобы убедиться, что это целое число.
- Номер на этой позиции твой номер? Если это так, остановитесь.
- Он больше или меньше?
- Если он больше, то число слева от него является новой максимально возможной позицией.
- Если он меньше, то число справа от него — это новая нижняя возможная позиция.
- Повторение.
Вот пример, который я написал на Python 3:
def binarysearch(lst, desired_value): lowest_index = 0 highest_index = len(lst) - 1 while lowest_index < highest_index: average = int((lowest_index + highest_index) / 2) if lst[average] == desired_value: return average elif lst[average] > desired_value: highest_index = average - 1 elif lst[average] < desired_value: lowest_index = average + 1 testLst =[2,3,4,5,10,12,33,100,150,300,220,110,4,6,7,1,400,45,99,350,124,11,222222,111] testLst.sort() correct_index = binarysearch(testLst, 33) print(testLst[correct_index] == 33)