Array meldet „nicht gefunden“, obwohl es gefunden wurde: ein verwirrendes Suchdilemma

Question

Dies ist eine häufige Frage und Antwort mit einem logischen Fehler, den ich in vielen Fragen sehe, die neue Programmierer in verschiedenen Sprachen stellen.

Das Problem besteht darin, ein Array nach Elementen zu durchsuchen, die bestimmten Eingabekriterien entsprechen. Der Pseudocode des Algorithmus lautet wie folgt:

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"

Dieser Code meldet „Nicht gefunden“, selbst wenn das passende Element erfolgreich gefunden wurde.

Answer 1

问题是，当您通过数组线性搜索某些内容时，直到到达数组末尾时您才知道没有找到它。问题中的代码针对每个不匹配的元素报告“未找到”，即使可能存在其他匹配元素。

简单的修改是使用一个变量来跟踪您是否发现了某些内容，然后在循环结束时检查该变量。

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 在其 for 循环中有一个 else: 块。仅当循环运行完成时才执行代码，而不是由于使用 break 而结束。这使您可以避免 found 变量（尽管它可能对以后的处理仍然有用）：

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

某些语言具有内置机制，可以使用这些机制来代替编写自己的循环。

• 某些语言具有 any 或 some 函数，它们接受回调函数，并返回一个布尔值，指示该函数对于数组的任何元素是否成功。
• 如果语言具有数组过滤功能，则可以使用检查条件的函数过滤输入数组，然后检查结果是否为空数组。
• 如果您尝试精确匹配某个元素，大多数语言都提供 find 或 index 函数来搜索匹配元素。

如果您要频繁搜索，最好将数组转换为可以更有效搜索的数据结构。大多数语言都提供集合和/或哈希表数据结构（后者根据语言有许多名称，例如关联数组、映射、字典），这些通常是搜索的时间为 O(1)，而扫描数组的时间为 O(n)。