Searching Algorithms Flashcards

All 14 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.

In a binary search, how is the position of the middle item worked out?

mid ← (start + finish) DIV 2, where start and finish are the first and last indexes still being searched. e.g. indexes 0 to 7: (0 + 7) DIV 2 = 3.

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.

In a binary search, how does the algorithm know that the item is not in the list?

The start position becomes greater than the finish position, so there are no items left to search.

In a binary search of a list in ascending order, how are start and finish changed when the middle item is not the target?

If the target is larger than the middle item, start ← mid + 1; if it is smaller, finish ← mid - 1.

The data in a list is not in order. Why might a linear search be a better choice than a binary search?

A binary search would need the list sorting first, and that sort takes time. If the data changes often or is searched only rarely, a linear search can be quicker overall.

On a short sorted list, how does the time a linear search takes compare with a binary search?

They take about the same time. A binary search only gives a real saving on large lists.