Поиск в массивах
10.02.2024
Поиск в массивах включает в себя линейный поиск и поиск максимального элемента.
Линейный поиск
Часто требуется в массиве найти заданное значение или, наоборот, сообщить, что его там нет. С этой целью просматриваются все элементы массива, начиная с первого и заканчивая последним элементом.
Этот алгоритм называют линейным поиском (поиск в массивах)
Рассмотрим решение одной задачи.
i = 0
while A [i] ! = X:
i += 1
print ("A[{}]={}". format(i, X))Данное решение работает, но только в случае, если нужный элемент в массиве есть, однако приведет к ошибке, если такого элемента нет, то такое решение приведет к ошибке. Это приведет к зацикливанию и выходу за границы массива.
Поэтому в условие нужно добавить еще одно ограничение: i <N, где через N обозначен размер массива. Если после окончания цикла это условие будет нарушено, то поиск был неудачным — элемента нет:
i = 0
while i < N and A[i] ! = X:
i += 1
if i < N:
print ("A[{}]={}".format(i,x))
else:
print ("Не нашли!")При i >=N элемента A[i] в массиве нет.
В этом случае проверка условия: А[i] ! = Х приведет к выходу за границы массива, и программа завершится аварийно.
Этого можно избежать.
В случае, если первая часть сложного условия с операцией end ложна, то вторая часть не проверяется, т.к. уже ясно, что всё условие тоже ложно. Поэтому в сложном условии:
i < N and A[i] != X
сначала нужно записать именно отношение i < N.
Если это условие ложно, то цикл завершится сразу.
Существует еще один подход к решению этой задачи. Используя цикл по переменной, можно перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение:
nX = -1
for i in range (N):
if A [i] == X:
nX = if
break
if nX >= 0:
print ( "A[{}] = { }".format (nX, X))
else:
print ( "Не нашли!")Для выхода из цикла используется оператор break, номер найденного элемента сохраняется в переменной nX. Если её значение осталось равным — 1 (не изменилось в ходе выполнения цикла), то в массиве нет элемента, равного X.
Последний пример можно упростить, используя особые возможности цикла for в языке Python:
for i in range (N):
if A [i] ==X:
print ("A[{}] = {}".format (i, X) )
break
else:
print ("Не нашли!")В этом месте выводим результат сразу, как только нашли нужный элемент, а не после цикла. Слово else после цикла for начинает блок/, который выполняется при нормальном завершении цикла ( без применения break).
В результате сообщение «Не нашли!» будет выделено только тогда, когда условие оператора if ни разу не выполниться.
В языке Python возможен и другой способ решения этой задачи, использующий встроенные методы для массивов (списков). Оператор in определяет, есть ли нужный элемент в массиве. Он возвращает логическое значение (True или False):
if X in A:
print ("Нашли!")
else:
print ("Не нашли!")А метод index возвращает индекс первого найденного элемента, равного Х:
nX = A.index(X)
print ("A[{}] = {}".format (i,X))
else:
print ("Не нашли!")Поиск максимального элемента в массиве (поиск в массивах)
Рассмотрим такой пример. Человеку необходимо выбрать самый большой арбуз из всех комнат, в которые заходит человек. При этом человек может нести только один арбуз.
Человек заходит в первую комнату и забирает из нее арбуз. Надо выбрать один арбуз. Поэтому человек берет арбуз и заходит во вторую комнату. Сравнивает арбуз в руках с весом арбуза во второй комнате и выбирает наибольший арбуз. Затем человек идет в третью комнату и т.д.
И так человек проходит все комнаты и выбирает самый большой арбуз.
На этой идее основан и поиск максимального элемента в массиве. Для хранения максимального элемента используем целочисленную переменную M.
На языке программирования Python этот алгоритм будет записан так:
for i in range (N):
if A[i] > M:
M = A [i]
print (M)Решим, каким должно быть натуральное значение М.
Можно записать в переменную М значение , которое будет точно меньше, чем любое значение элементов массива. Например, если в массиве записаны натуральные числа, можно записать в М ноль (максимальный элемент всегда будет больше нуля).
Если содержимое массива неизвестно, можно сразу записать в М значение А [0] (сразу взять первый арбуз), а цикл перебора начать со второго по счету элемента А[1]:
M = A[0]
for i range (1, N):
if A[i] > M: M = X
print (M)Наиболее аккуратно будет смотреться вариант с другим типом цикла for:
M = A [0]
for x in A:
if x > M: M = x
print (M)Далее надо найти номер максимального элемента. Один из варианта поиска следующий: вводим еще одну переменную nMax для хранения номера, сначала записать в нее 20 (считаем первый элемент максимальным) и затем, когда найдем новый максимальный элемент, запомнить его номер в переменной nMax:
M = A[0]
for i in range (1, N):
if A[i] > A [nMax]:
nMax = i
print("A[{}] = {}".format (nMax, A[nMax]))Для поиска максимума можно использовать и встроенные функции Python: сначала найти максимальный элемент, а потом его индекс с помощью функции index:
M = max(A)
nMax = A.index (M)
print ("A[{}] = {}".format(nMax, M))В этом случае фактически придется выполнить два прохода по массиву. Однако такой вариант работает быстрее, чем «рукописный» цикл с одним проходом, потому что встроенные функции написаны на языке С++ и подключаются в виде машинного кода, а не выполняются относительно медленным интерпретатором Python.
Экономист по первому образованию и учитель информатики по второму. Преподаю в школе информатику, программирование, сайтостроение, экономику.