Understanding the Problem: Linear Search From Scratch
This problem asks you to implement the most fundamental search operation in computer science: checking whether a value exists in an unsorted array. Python's built-in in operator does exactly this behind the scenes — but here you'll write the logic yourself so you truly understand what's happening.
This is called a linear search: scan each element one by one until you find a match or exhaust the list. It's the right tool when data is unsorted and no smarter structure is available.
The Core Insight
You need to loop through every element and ask: "Is this the one I'm looking for?" The moment you find it, you're done — return True immediately (no need to keep searching). If you reach the end without a match, return False.
This "early exit" pattern is important for efficiency — never do more work than necessary.
Step-by-Step Algorithm
- Loop through every element
numinnums. - At each step, compare
numtovalue. - If they match, immediately
return True. - If the loop ends without a match,
return False.
Code Implementation
def contains(nums, value):
for num in nums:
if num == value:
return True # found it — stop searching immediately
return False # reached the end without finding it
# Examples:
print(contains([1, 2, 4, 5], 4)) # True
print(contains([-1, 2, -4, 0, 10], 7)) # False
print(contains([], 5)) # False (empty list)
Complexity Analysis
- Time: O(n) — In the worst case (value not present, or at the very end), we check every element once. With n elements, that's n comparisons.
- Space: O(1) — We only use a single loop variable, regardless of input size. No extra data structures needed.
This is the best possible time complexity for searching an unsorted array — you can't do better than O(n) without sorting first or using a hash set.
Edge Cases to Consider
# Empty array → always False:
contains([], 1) # False — loop doesn't execute
# Single element — match:
contains([7], 7) # True
# Single element — no match:
contains([7], 3) # False
# Value appears multiple times — still True (early exit after first match):
contains([1, 2, 3, 1], 1) # True
# Negative numbers:
contains([-5, 0, 5], -5) # True
Why Not Just Use the `in` Operator?
Python's value in nums does exactly what this function does — it's clean, Pythonic, and you should use it in production code. But implementing it yourself teaches you:
- What O(n) linear search actually means in practice
- How early exit improves average-case performance
- The foundation you need to understand faster alternatives like binary search (O(log n)) and hash sets (O(1))
Key Takeaways
- Linear search iterates through every element — O(n) time, O(1) space.
- Return
Trueimmediately upon finding a match — don't keep looping. - Return
Falseonly after the loop completes with no match. - Always test edge cases: empty array, single element, value not present, duplicates.
What to Learn Next
Linear search works on any array, sorted or not. But if your data is sorted, binary search can find a value in O(log n) time — dramatically faster for large arrays. Next, try implementing binary search and see how a sorted structure changes the entire strategy.
