Binary Search

Binary search is a search algorithm that finds a target in a sorted collection by repeatedly checking the middle item and throwing away about half of what is left. Because each comparison discards about half of the remaining items, it is called a divide-and-conquer algorithm. If the collection is not sorted, binary search cannot be used: the discarding only works because items before the middle are smaller than it and items after it are larger.

How each comparison works

The search keeps a start index and an end index that mark the current search area. Find the midpoint by adding start and end and dividing by two; rounding down or up is fine as long as you do the same every time. Compare the middle item with the target:

• If they are equal, the search ends successfully.
• If the target is before the middle item, discard the middle item and everything after it, then move the end index to just before the old midpoint.
• If the target is after the middle item, discard the middle item and everything before it, then move the start index to just after the old midpoint.

The middle item itself is never kept in the remaining sublist: the updated start or end index leaves it out.

After every discard, recalculate the midpoint from the new start and end. Keep going until the target is found or the search area is empty. The area is empty when the start index has passed the end index, which means the target is not in the collection.

Worked example

Locker numbers stored in order: 4, 9, 15, 22, 30, 38, 41, 57, 63, 88. Indexes run from 0 to 9. Search for 57.

The first comparison threw away five of the ten items, which is why binary search is fast on large sorted collections.