Linear search idea
- Algorithms course
- Beginner
- Lesson 13/80
- 4 min
Scan an array front to back to find a target in O(n).
Linear search logic
Linear search is the simplest way to find a target in an array: it checks every element in order from start to end.
If an element equals the target, its index is returned. If the end is reached without a match, -1 is returned.
Complexity analysis
The worst case of linear search is O(n): if the target is last, the whole array is scanned. The best case is O(1): if the target is first.
The average case is also O(n) because the target is on average in the middle and half the array is scanned.
Practice Linear search
Write linear_search(arr, target). Find target, return index; -1 if not found. Print 2 with print(linear_search([4, 2, 7, 1], 7)).
Starter code
def linear_search(arr, target):
# Search for targetSample solution
def linear_search(arr, target):
# Search for target
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
print(linear_search([4, 2, 7, 1], 7))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the worst case of linear search?
- O(1) Correct answer
- O(log n)
- O(n)
- O(n^2)
Explanation: The worst case is O(n).
2 Not found value
If the target is not found, ____ is returned.If the target is not found, -1 is returned.Explanation: -1 is right.
3 Linear search idea: match the terms
| Term | Meaning |
|---|---|
Linear search |
Check in order |
O(n) |
Worst case |
O(1) |
Best case |
-1 |
Not found |