搜索数组报告"未找到"即使已找到

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