Array reports "not found" despite being found: a confusing search dilemma

Question

This is a common question and answer with a logic error that I see in many questions asked by new programmers in various languages.

The problem is to search an array for elements that match certain input conditions. The pseudocode of the algorithm is as follows:

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 will report "not found" even if the matching element is successfully found.

Answer 1

The problem is that when you linearly search for something through an array, you don't know it wasn't found until you reach the end of the array. The code in the question reports "Not Found" for each unmatched element, even though there may be other matching elements.

A simple modification would be to use a variable to keep track of whether you found something, and then check that 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 has an else: block in its for loop. The code is only executed when the loop has finished running, not when it ends using break. This allows you to avoid the found variable (although it may 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 loops.

• Some languages ​​have any or some functions that accept a callback function and return a boolean value indicating whether the function was successful for any element of the array.
• If the language has array filtering capabilities, you can filter the input array using a function that checks the condition, and then checks whether the result is an empty array.
• If you are trying to match an element exactly, most languages ​​provide a find or index function to search for a matching element.

If you will be searching frequently, it is best to convert the array into a data structure that can be searched more efficiently. Most languages ​​provide sets and/or hashtables data structures (the latter have many names depending on the language, e.g. associative arrays, maps, dictionaries), and these are usually the ones where searches are done is O(1), while the time to scan the array is O(n).