Comparing Linear & Binary Search Flashcards

All 6 cards in this deck

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.

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.

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.

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.