Как быстро найти число в массиве?
Последовательный просмотр
В задачах ЕГЭ по информатике часто требуется узнать, присутствует ли в массиве определенное число или нет.
Если массив a небольшой, то можно просто просмотреть все элементы и сравнивать по очереди наше число x с каждым из них:
n = len(a)
present = False
for i in range(n):
if a[i] == x:
present = True
break
После завершения цикла переменная present будет иметь значение True, если данное число есть в массиве.
Впрочем, можно воспользоваться встроенной операцией языка Питон in:
x in a
Это выражение можно использовать в условиях условных операторов и циклов ("if x in a:") или присвоить его значение переменной.
Однако если наш массив большой (скажем, миллион элементов) и поиск элемента нужно выполнять многократно, то такой метод - неприемлемо медленный.
Двоичный поиск
Выход - в использовании двоичного поиска. Правда, этот метод работает только в том случае, если наш массив отсортирован по возрастанию. (Сортировка больших массивов - это тема для отдельного разговора.)
Идея двоичного поиска крайне проста. Мы будем использовать две переменные: top и bottom. Сначала присвоим переменной top значение 0, а переменной bottom - индекс последнего элемента в массиве (len(a)-1).
Теперь вычислим индекс элемента посередине между top и bottom:
middle = (top+bottom)//2
Сравним значение элемента a[middle] и числа x. Если они равны - мы нашли наше число в массиве. Если x больше, чем a[middle] - то наше число может находиться только между элементами a[middle+1] и a[top], поэтому выполняем присваивание bottom=middle+1. Если же x меньше a[middle], то интервал индексов для элемента со значением x - от bottom до middle-1, и мы выполняем присвоение top=middle-1.
Выполняем этот шаг, пока bottom<=top. Если в итоге top окажется меньше bottom, то искомого числа в массива нет.
Алгоритм очень быстрый: поиск числа в массиве из тысячи элементов требует максимум 10 шагов, а в массиве из миллиона - 20. (На каждом шаге количество элементов, среди которых может находиться наше число x, сокращается вдвое.)
Приведем данный алгоритм, оформленный в виде функции:
def binsearch(a,x):
bottom = 0
top = len(a)-1
while bottom <= top:
middle = (bottom+top)//2
if a[middle] == x: return middle
if a[middle] < x: bottom = middle + 1
else: top = middle - 1
return -1
Если число x присутствует в массиве, то функция возвращает индекс соответствующего элемента. Если же число не найдено, то функция возвращает число -1.
Иногда нужно знать, сколько элементов массива строго меньше числа x. Двоичный поиск помогает решить и эту задачу. Предполагаем, что массив a отсортирован по возрастанию и все числа в нем различны. Тогда ответ на вопрос может дать функция с практически аналогичным кодом (разница лишь в последней строке):
def binsearchless(a,x):
bottom = 0
top = len(a)-1
while bottom <= top:
middle = (bottom+top)//2
if a[middle] == x: return middle
if a[middle] < x: bottom = middle + 1
else: top = middle - 1
return top+1
(Вместо return top+1 в последней строке можно было написать return bottom).
Если массив а = [3, 5, 8, 12], то значение x=2 даст результат 0, значение x=3 - тоже 0, значение x=6 - результат 2, а x=15 - 4.
Ещё одно замечание. Если требуется знать, сколько элементов массива меньше или равно указанному числу (а не строго меньше), то вместо строки
if a[middle] == x: return middle
надо написать
if a[middle] == x: return middle+1
Если в массиве есть повторяющиеся элементы, то задача нахождения числа элементов, которые строго меньше указанного числа (или меньше или равны), усложняется. Придется просмотреть элементы массива в окрестности найденного элемента.
(c) Ю.Д.Красильников, 2021 г.
Комментарии
Отправить комментарий