search - Searching array reports "not found" even though it's found

Question

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.

Answer 1

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

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

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