search — Поиск по массиву отчетов & quot; не найден & quot; хотя он найден

Question

search — Поиск по массиву отчетов & quot; не найден & quot; хотя он найден

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

Проблема заключается в поиске в массиве элемента, который соответствует некоторым критериям ввода. Алгоритм в псевдокоде выглядит примерно так:

for each element of Array:
if element matches criteria:
do something with element
maybe break out of loop (if only interested in first match)
else:
print "Not found"

Этот код сообщает «Не найдено», даже если он успешно находит соответствующий элемент.

1

arrays language-agnostic search

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Проблема в том, что когда вы ищете что-то линейно в массиве, вы не можете знать, что оно не найдено, пока не достигнете конца массива. Код в вопросе сообщает «Не найдено» для каждого несоответствующего элемента, хотя могут быть и другие соответствующие элементы.

Простая модификация состоит в том, чтобы использовать переменную, которая отслеживает, нашли ли вы что-то, а затем проверить эту переменную в конце цикла.

found = false
for each element of Array:
if element matches criteria:
do something with element
found = true
maybe break out of loop (if only interested in first match)

if not found:
print "Not found"

Python имеет else: блок в его for петли. Это выполняет код, только если цикл выполняется до завершения, а не до конца из-за использования break, Это позволяет избежать found переменная (хотя это может быть полезно для дальнейшей обработки):

for element in someIterable:
if matchesCriteria(element):
print("Found")
break
else:
print("Not found")

Некоторые языки имеют встроенные механизмы, которые можно использовать вместо написания собственного цикла.

Некоторые языки имеют any или же some функция, которая принимает функцию обратного вызова и возвращает логическое значение, указывающее, успешно ли выполняется какой-либо элемент массива.
Если в языке есть функция фильтрации массива, вы можете отфильтровать входной массив с помощью функции, которая проверяет критерии, а затем проверяет, является ли результат пустым массивом.
Если вы пытаетесь точно сопоставить элемент, большинство языков find или же index функция, которая будет искать соответствующий элемент.

Если вы будете часто выполнять поиск, может быть лучше преобразовать массив в структуру данных, в которой можно искать более эффективно. Большинство языков обеспечивают set и / или hash table структуры данных (последняя имеет много имен в зависимости от языка, например, ассоциативный массив, карта, словарь), и они обычно доступны для поиска за O (1) времени, в то время как сканирование массива O (n).

6