Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A club keeps its eight members in an array in the order they joined: Ines, Kofi, Hana, Luis, Ama, Pavel, Sara and Yuki. A linear search starts at the first name.
Linear search: compare each item in turn from the first; stop when it is found or the list ends. Bubble sort: compare each pair of neighbours and swap them if they are in the wrong order; repeat passes until a pass makes no swaps. A pass over items makes comparisons at most.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Ama is at index . The search compares Ines, Kofi, Hana, Luis and then Ama: comparisons.
Step 2. Bruno is not in the list, so every one of the names is compared before the search can say "not found".
Answer: (a) ; (b) .
What if? If the club sorted its list by name, a linear search would still work. The number of comparisons would change, because the order changes.
Log in to join the discussion.
Loading…