Searching in Lists

Concepts covered: List Search

Searching a list means asking whether a value is there and, if it is, where it sits and how many times it appears. in checks for the value, while index() finds its position and count() counts it. Underneath, they work the same way: start at position 0 and compare each item with == until the answer is known.

statuses = ["ok", "ok", "late", "ok", "failed", "late"]

print("failed" in statuses)
print("missing" in statuses)
print("missing" not in statuses)
print(statuses.index("late"))
print(statuses.count("late"))
print(statuses.count("missing"))

Output:

True
False
True
2
2
0

in returns True or False, and not in returns the opposite, which reads well in a guard clause. index() returns the position of the first match only, so the second "late" at position 5 is never reported. count() returns how many items equal the value, and 0 when none do.

statuses = ["ok", "ok", "late", "ok", "failed", "late"]


def first_position(items, target):
    for i, item in enumerate(items):
        print(f"check {i}: {item}")
        if item == target:
            return i
    return None


print(first_position(statuses, "failed"))
print(statuses.index("failed"))
print(statuses.count("late"))

check 0: ok
check 1: ok
check 2: late
check 3: ok
check 4: failed
4
4
2

The animation shows the work behind every search. Finding "failed" takes 5 checks because it sits at position 4, and the loop stops at the first match. A value near the front costs a few checks; a value near the end, or one that is missing, costs a check for every item. On a list of a few hundred items nobody notices. Inside a loop that tests each incoming record against a list of 1,000,000 IDs, every missing ID costs 1,000,000 comparisons, and a later lesson covers structures built for fast lookups.

index() raises when the value is missing

statuses.index("missing") raises ValueError: 'missing' is not in list, which stops the program. Check with in first, or use a loop that returns None when nothing matches, as the animation's function does. index() also accepts a starting position: statuses.index("late", 3) begins searching at position 3 and returns 5, the second late batch.

statuses = ["ok", "ok", "late", "ok", "failed", "late"]

def find(items, target):
    if target not in items:
        return None
    return items.index(target)

print(find(statuses, "failed"))
print(find(statuses, "missing"))
print(statuses.index("late", 3))

positions = []
for i, status in enumerate(statuses):
    if status == "late":
        positions.append(i)
print(positions)

Output:

4
None
5
[2, 5]

The guard in find() turns a crash into a None the caller can test with is None, at the cost of scanning the list twice when the value is present. The enumerate() loop at the end collects every matching position, which index() alone cannot do.

Searching by a condition

in and index() look for one exact value. To find the first item that meets a condition, such as the first day with fewer than 100 rows, write the loop yourself and stop with break. The loop's else runs only when the loop finished without breaking, which is exactly the not-found case.

daily_rows = [120, 135, 98, 160, 142, 155, 171, 149]

for day, rows in enumerate(daily_rows, start=1):
    if rows < 100:
        print(f"first short day: day {day} with {rows} rows")
        break
else:
    print("no short days")

for day, rows in enumerate(daily_rows, start=1):
    if rows > 200:
        print(f"first spike: day {day}")
        break
else:
    print("no spikes")

Output:

first short day: day 3 with 98 rows
no spikes

What counts as a match

print(1.0 in [1, 2, 3])
print("1" in [1, 2, 3])
print([2, 5] in [[1, 0], [2, 5]])
print(2 in [[1, 0], [2, 5]])
print("ok" in ["ok_retry", "okay"])

Output:

True
False
True
False
False

Every search compares with ==, so the equality rules from comparing lists decide what matches. The float 1.0 equals the integer 1 and is found. The string "1" doesn't equal the integer 1, which is how IDs read from text quietly fail to match IDs stored as numbers. An item can itself be a list, and [2, 5] matches only a whole item equal to it, so 2 isn't found even though it appears inside an item. On a list of strings, in matches whole items: "ok" is not found in ["ok_retry", "okay"], while in on a single string finds substrings.

What does this program print?

ids = [104, 220, 104, 315]
target = "104"
if target in ids:
    print(ids.index(target))
else:
    print("not found")
print(ids.count(104))

• 0 then 2
• A ValueError from index()
• not found then 2
• not found then 1

Do

• Guard index() with in when the value might be missing
• Convert IDs to one type before searching a list of IDs
• Pass a start to index() to step past a match you already handled
• Use a loop with break and else to find the first item meeting a condition

Avoid

• Don't expect index() to report more than the first match
• Don't run in against a huge list once per record inside a loop
• Don't expect in on a list to match part of a string item
• Don't count matches with a loop when count() does it in one call

About this lesson

This section is part of the Lists: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.