搜索数组报告“找不到”，即使找到了

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