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

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