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

Итак, представим простую задачу: у нас есть массив, состоящий из 10 чисел: [1, 6, 3, 9, 0, 23, 5, 55, -23, 7]. Необходимо найти индекс элемента со значением -23. 

Первое наивное решение, которое приходит в голову, пройтись по всем элементам массива, сравнивая их с искомым числом. Если текущий элемент не равен числу, двигаемся дальше, иначе мы нашли искомое число и возвращаем его индекс. Простой алгоритм на Python выглядит так:

nums = [1, 6, 3, 9, 0, 23, 5, 55, -23, 7]  # объявляем список

target = 23  # искомое число
for i in range(len(nums)):  # проходимся по nums через индекс i 
    if nums[i] == target:  # проверка на совпадание
        print(i)  # выводим индекс искомого числа
        exit()  # завершаем программу
print(-1)  # если числа нет в массиве, выводим -1

Для лучшего понимания посмотрим принцип работы алгоритма на видео:

Рабочее решение! Но есть нюансы. Проблема данного алгоритма заключается в том, что скорость поиска элемента в массиве линейно зависит от количества элементов в нем. Проще говоря, если количество элементов будет, например, 10^5, то алгоритм уже не так быстро выведет ответ. Асимптотическая сложность данного алгоритма - O(n).

Для более эффективного решения воспользуемся идеей бинарного поиска. 

В чем его суть?

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

Пример:

У нас есть массив отсортированных чисел, например, n = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], и мы хотим найти число 6. Первое, что нужно сделать - поставить указатели на начальный и последний индексы массива. Пусть на нулевом индексе стоит указатель L, равный 0, а на последнем индексе - указатель R, равный 9. Далее проверим элемент с индексом M = (L + R) / 2, является ли он искомым числом. Если наше число больше, то мы двигаем указатель L на позицию M, если наше число меньше, то двигаем указатель R влево, если же nums[M] равен искомому числу, то завершаем программу. 

В случае нашего примера число 5 < 6, значит, двигаем указатель L вправо на позицию M. Следующий шаг M = (L + R) / 2 => M = 6, nums[M] = 7. Так как 7 > 6, двигаем правый указатель на индекс 6.

Снова считаем среднее M = (L + R) / 2 => M = 5, nums[M] = 6, мы нашли искомое число.

Асимптотическая сложность бинарного поиска равна O(log_n). Код на Python выглядит так:

nums = sorted([9, 2, 7, 4, 10, 6, 8, 3, 1, 5]) # объявляем список и сортируем его
l = -1 # ставим указатель на индекс -1
r = len(nums) - 1 # ставим указатель на индекс 9
target = 6 # объявляем переменную с искомым числом

while l + 1 != r: 
    m = (l + r) // 2 # считаем среднее
    # если значение по индексу среднего числа меньше искомого, двигаем указатель вправо 
    if nums[m] < target: 
        l = m
    else:
        r = m

print(r)

Также рассмотрим принцип работы алгоритма на видео:

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

Бинарный поиск используется не только для поиска индекса конкретного числа, но и также его можно использовать для: 

1. для нахождения первого / последнего числа в подпоследовательности из подряд идущих одинаковых чисел. Например, бин. поиск сможет определить индекс последнего элемента подпоследовательности, состоящей из числа 5, в массиве [1, 4, 5, 5, 5, 5, 5, 9, 13]

2. для нахождения корней уравнений 

3. для поиска числа по ответу

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

Мы рассмотрели принцип реализации линейного и бинарного поиска, разобрали принципы их работы и эффективность этих алгоритмов. Хочется отметить, что каждый из алгоритмов стоит использовать, учитывая входные данные. Говоря другими словами, каким бы ни был эффективным бин. поиск, не обязательно его применять, если вы ищете элемент в массиве, состоящем только из 100 элементов.

Больше пользы для тебя ты можешь найти в моём открытом Telegram-сообществе: подписаться