Linear search
Looking for a value by checking the cells one by one: stopping as soon as it is found, the index returned or the not-found value, the first occurrence and the number of comparisons.
- 24 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Linear search: what is it?
Show the answer
An algorithm that compares the sought value with the items in order, cell after cell, requiring nothing of the array's order.
It works on any array, sorted or not. Its cost is proportional to the size: in the worst case, every cell is looked at.
What does this program print?
```python
def find(t, v):
for i in range(len(t)):
if t[i] == v:
return i
return -1
print(find([5, 12, 8, 12, 3], 12), find([5, 12, 8], 7))`1 -13 -11 02 -1
Show the answer
1 -1The first call stops at the first occurrence of 12, index 1. The second checks the three cells without success and reaches the
return -1placed after the loop.In the worst case, a linear search in an array of n cells makes … comparisons, whether the value is … or in the last cell.
Show the answer
In the worst case, a linear search in an array of n cells makes n comparisons, whether the value is absent or in the last cell.
In both cases, every cell must be checked before concluding. In the best case, the value is in the first cell: a single comparison.
Early exit: what is it?
Show the answer
Stopping a loop as soon as its goal is reached, without visiting the remaining items:
returnorbreak.Once the value is found, looking at the rest is pointless. Without an early exit, a loop that writes
pos = ion every success would return the last occurrence instead of the first.