Standard Searching Algorithms Flashcards

All 7 cards in this deck

What are the main steps of a linear search?
e.g. search 4, 9, 2, 7 for the value 2

1. Compare the first value to the value searched for: $4 \neq 2$.
2. If they match, stop — the item is found.
3. If not, move to the next value and repeat: $9 \neq 2$, then $2 = 2$ → found.

What are the main steps of a binary search?
e.g. find 10 in 1, 2, 5, 6, 7, 10, 20

1. Pick out the middle value: 6.
2. If it is not the value searched for, discard the half it cannot be in: $6 < 10$, so discard 1, 2, 5, 6 and keep 7, 10, 20.
3. Repeat on the remaining list: middle value is 10 → found.

State one pre-requisite for a binary search.

The data must be sorted / in order.

True or false? A linear search can only be used on data that is in order.

False. A linear search works on unsorted data; only a binary search needs sorted data.

Other than finding the value, what condition stops a linear search?

The end of the list is reached / every value has been checked (and the value was not found).

Which search would you choose for a large list that is already sorted, and why?

Binary search — it halves the list each time, so it needs far fewer comparisons than a linear search.

True or false? Each comparison in a binary search discards about half of the remaining items.

True. The middle item is compared, then one half of the list is discarded, which makes it faster than a linear search on large sorted lists.