搜索数组报告“未找到”，即使它已找到

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 在其

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