Основой изучения информатики является анализ алгоритмов и структур данных. Это может звучать пугающе и вызывать образы гениев-математиков, выписывающих на доске эзотерические символы, но я могу заверить, что это не так.

Алгоритм — это просто последовательность шагов, которые всегда заканчиваются желаемым результатом. Бинарный поиск — это один из алгоритмов, которым учат новичков, потому что он помогает понять истинную красоту информатики. Двоичный поиск — это сокращение времени, необходимого для поиска фрагмента данных. Для небольших наборов данных время может быть несерьезным фактором, но когда вам нужно искать наборы данных с тысячами или миллионами элементов, выбор, эффективный с точки зрения времени, может быть разницей между успехом и неудачей.

Вот пример бинарного поиска. Скажем, у вас есть отсортированный список чисел: [10,30,50,99,100,150,600]. И вы хотите найти позицию числа «150». Что ж, вы могли бы сделать это, проходя одно за другим через весь список чисел, но если бы этот список состоял из 1 000 000 элементов, вы бы делали это очень долго. Мы можем сэкономить много времени, выполнив следующие шаги:

  1. Найдите среднюю позицию в списке, взяв среднее значение самой низкой позиции и самой высокой позиции. Округлите в меньшую сторону, чтобы убедиться, что это целое число.
  2. Номер на этой позиции твой номер? Если это так, остановитесь.
  3. Он больше или меньше?
  4. Если он больше, то число слева от него является новой максимально возможной позицией.
  5. Если он меньше, то число справа от него — это новая нижняя возможная позиция.
  6. Повторение.

Вот пример, который я написал на 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)