尽管已找到，阵列仍报告'未找到”：令人困惑的搜索困境

Question

这是一个逻辑错误的通用问题和答案，我在新程序员用各种语言提出的许多问题中都看到过。

问题是在数组中搜索与某些输入条件匹配的元素。该算法的伪代码如下所示：

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"

即使成功找到匹配元素，此代码也会报告“未找到”。

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)。