Binary Search Flashcards

All 6 cards in this deck

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? 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.

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.