Summary - Linear search
- Algorithms course
- Beginner
- Lesson 16/80
- 4 min
Call linear search and print the result in a mini task.
Summary - Linear search
In this group you learned the logic, implementation and complexity analysis of linear search. Worst case is O(n), best case is O(1).
Linear search is simple but slow on large arrays. On sorted arrays, binary search is faster.
Practice First occurrence index
Write find_index(arr, target). Return first index of target; -1 if absent. Print 0 with print(find_index([5, 3, 5, 7], 5)).
Starter code
def find_index(arr, target):
# Find first indexSample solution
def find_index(arr, target):
# Find first index
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
print(find_index([5, 3, 5, 7], 5))Expected output
0
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Linear search: match the terms
| Term | Meaning |
|---|---|
Linear search |
Check in order |
O(n) |
Worst |
O(1) |
Best |
-1 |
Not found |
2 Linear search
Question
Linear search checks every element ____.
Answer
Linear search checks every element one by one.Explanation: one by one is right.
3 On which array does linear search work?
- Only sorted
- Only unsorted
- Both sorted and unsorted
- Only empty Correct answer
Explanation: Linear search works on any array.