What is wrong with this Python function?
def find(items, target):
for i in range(len(items)):
if items[i] == target:
return i
else:
return -1
ANothing; it is a correct linear search
BIt checks only the first element, because both branches return during the first pass of the loop
CIt skips the first element
DIt returns the last match instead of the first
On the first iteration, either the if or the else returns, so the loop never reaches index 1. The return -1 belongs after the loop, so it runs only when every element has been checked without a match.
Question 2 Multiple Choice
A linear search runs on an unsorted array of 1,000 distinct values. What is the largest number of element comparisons it can make?
A10
B500
C1,000
D1,000,000
In the worst case the target is in the last position or absent, so every one of the 1,000 elements is compared once. About 10 is the worst case for binary search on a sorted array of this size, and 500 is roughly the average for a target that is present.
Question 3 True / False
Because binary search is O(log n) and linear search is O(n), it is always faster to sort an unsorted list and then binary search it than to run one linear search.
TTrue
FFalse
Answer: False
A comparison sort takes O(n log n) time, which is more than the O(n) of a single linear search. Sorting pays off only when the same data will be searched many times.
Question 4 Short Answer
A list contains the target value at indexes 3, 7 and 12. A standard linear search that returns as soon as it finds a match is run on it. Which index does it return, and why?
Think about your answer, then reveal below.
Model answer: It returns 3, because it checks indexes in increasing order and stops at the first element that matches.
Linear search finds the first occurrence. To find all occurrences, the loop must keep going and collect every matching index instead of returning early.