Standard Searching Algorithms Flashcards
Card 1 of 10
All 10 cards in this deck
What are the main steps of a linear search?
e.g. search 4, 9, 2, 7 for the value 2- Compare the first value to the value searched for: .
- If they match, stop — the item is found.
- If not, move to the next value and repeat: , then → found.
What are the main steps of a binary search?
e.g. find 10 in 1, 2, 5, 6, 7, 10, 20- Pick out the middle value: 6.
- If it is not the value searched for, discard the half it cannot be in: , so discard 1, 2, 5, 6 and keep 7, 10, 20.
- 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.
In a binary search, which item is the middle one when the list has an even number of items?
There are two central items and either can be used, e.g. item 4 or item 5 of 8. One common rule is position , rounded up.
Give one drawback of a linear search.
It is slow on large lists, because in the worst case every item has to be checked.
Apart from not needing the list to be sorted, give one advantage of a linear search over a binary search.
It is simpler to write and understand.