搜索阵列报告“未找到"即使它被发现 [英] Searching array reports "not found" even though it's found

问题描述

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

This is a generic question and answer for a logical error I've seen in many questions from new programmers in a variety of languages.

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

The problem is searching an array for an element that matches some input criteria. The algorithm, in pseudo-code, looks something like this:

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"

此代码即使成功找到匹配元素也会报告未找到".

This code reports "Not found" even if it successfully finds a matching element.

推荐答案

问题在于，当你通过数组线性搜索某物时，你无法知道它没有找到，直到到达数组的末尾.问题中的代码为每个不匹配的元素报告未找到"，即使可能有其他匹配的元素.

The problem is that when you're searching for something linearly through an array, you can't know that it's not found until you reach the end of the array. The code in the question reports "Not found" for every non-matching element, even though there may be other matching elements.

简单的修改是使用一个变量来跟踪你是否发现了什么，然后在循环结束时检查这个变量.

The simple modification is to use a variable that tracks whether you found something, and then check this variable at the end of the loop.

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 变量(尽管它可能仍然对以后的处理有用):

Python has an else: block in its for loops. This executes code only if the loop runs to completion, rather than ending due to use of break. This allows you to avoid the found variable (although it might still be useful for later processing):

for element in someIterable:
    if matchesCriteria(element):
        print("Found")
        break
else:
    print("Not found")

某些语言具有可以使用的内置机制，而无需编写自己的循环.

Some languages have built-in mechanisms that can be used instead of writing your own loop.

• 有些语言有一个 any 或 some 函数，它接受一个回调函数，并返回一个布尔值，指示它对数组的任何元素是否成功.
• 如果语言有数组过滤功能，可以用检查条件的函数过滤输入数组，然后检查结果是否为空数组.
• 如果您想精确匹配一个元素，大多数语言都提供了一个 find 或 index 函数来搜索匹配的元素.

• Some languages have an any or some function that takes a callback function, and returns a boolean indicating whether it succeeds for any elements of the array.
• If the language has an array filtering function, you can filter the input array with a function that checks the criteria, and then check whether the result is an empty array.
• If you're trying to match an element exactly, most languages provide a find or index function that will search for a matching element.

如果您要频繁搜索，最好将数组转换为可以更有效搜索的数据结构.大多数语言提供 set 和/或 hash table 数据结构(后者根据语言有很多名称，例如关联数组、映射、字典)，这些通常是可在 O(1) 时间内搜索，而扫描数组则为 O(n).

If you'll be searching frequently, it may be better to convert the array to a data structure that can be searched more efficiently. Most languages provide set and/or hash table data structures (the latter goes under many names depending on the language, e.g. associative array, map, dictionary), and these are typically searchable in O(1) time, while scanning an array is O(n).

这篇关于搜索阵列报告“未找到"即使它被发现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！