Implementing search
- Algorithms course
- Beginner
- Lesson 14/80
- 4 min
Turn linear search into pseudocode returning an index.
Search implementation
Implementing linear search requires a for loop and an if condition. The loop visits each element; the condition checks equality.
If equality is found, return i immediately returns the index. The loop does not continue because the search is complete.
Early exit
Linear search exits the loop as soon as the target is found. This gives O(1) in the best case: if the target is first, one comparison suffices.
Thanks to early exit, the average case is O(n/2) but Big-O ignores constant factors, so the average is also written O(n).
Practice Count value
Write count_value(arr, target). Count occurrences and return. Print 3 with print(count_value([1, 2, 2, 3, 2], 2)).
Starter code
def count_value(arr, target):
# Count occurrencesSample solution
def count_value(arr, target):
# Count occurrences
count = 0
for x in arr:
if x == target:
count = count + 1
return count
print(count_value([1, 2, 2, 3, 2], 2))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Equality check
Equality in array: if arr[i] == ____Equality in array: if arr[i] == targetExplanation: target is right.
2 Implementing search: match the terms
| Term | Meaning |
|---|---|
for |
Loop |
if |
Condition |
return i |
Found |
return -1 |
Not found |
3 What happens when the target is found?
- Loop continues
- Error is raised
- Index is returned Correct answer
- Array is deleted
Explanation: The index is returned.