Show the best case and the worst case of searching a list for a value, and explain what changes between them.
The best case is when the answer is the first thing you look at, and the worst case is when the answer is the last thing or is not there at all.
def find(items, target):
for i, value in enumerate(items):
if value == target:
return i
return -1
So here is what changes between them. In the best case, the target is the first item, so the loop runs once and one comparison is made. In the worst case, the target is the last item or is not in the list at all, so the loop runs n times and n comparisons are made.
And in between there is the average case, where the target is in a random place, so the loop runs about half the length of the list and makes about n over two comparisons.
There is one more thing that changes, and it is about the space as well. The best case needs only one comparison, so it needs very little memory. The worst case has been through the whole list, and any temporary values it made along the way are still there, so it needs more. That is usually not the thing that decides anything, but it is worth knowing that the cases are different in more than one way.
The next question in this topic compares the two searches, and the last one explains a surprising result about quicksort.