Binary Search algorithm

#zettel/permanent

The idea

Binary Search algorithm
The binary search algorithm aims to find a target value inside a collection. It has time complexity of O(log n) (logarithmic time complexity).

In order for this algorithm to work properly, the collection needs to be sorted. Otherwise, the target value might be wrongfully discarded in the process.

These are the steps for the algorithm:

  1. Get the element in the middle of the collection.
  2. Check if the middle element is the target. If it is, the algorithm is done.
  3. If the target value is lower than the midpoint, the upper half of the collection is discarded. The lower half will be the new list.
  4. If the target is higher than midpoint, the upper half is used instead.
  5. Those steps are repeated until the target is found or the remaining list only has one element.
  6. If the last element is not the target, then it wasn't on the list.

Relations

Sources