Binary Search

The word binary (from the word two) refers to anything with two possible options or parts. A binary search involves binary decisions - decisions with two choices.

The underlying idea of a binary search is to divide one's data in half and to examine the data at the point of the split. If the data is sorted, it's very easy and efficient to ignore one half or the other half of the data, depending on where the value that is being searched is located.

Assuming that a list is already sorted, a target value is searched for by repeating the following steps: - Divide the list in half. - Examine the value in the middle of the list. Is the target value equal to the value there, or does it come before or after the center value? If the target value comes before or after, then return to step a, to repeat the process with the halved list where the target value is located.

For example, with a list of 1,024 sorted values, we happen to be searching for a target value that is stored in position 492. Using a binary search, the list of 1,024 is split in half; because the target value is not found in position 512, we proceed to search the first half (and discard the values in the second half). Within the sublist from 1...512, we do another binary search sequence: split; examine; and binary search again.

The speed of a binary search comes from the elimination of half of the data set each time. If each arrow below represents one binary search process, only ten steps are required to search a list of 1,024 numbers:

The log₂1024 is 10. In a worst-case scenario, if the size of the list doubled to 2,048, only one more step would be required using a binary search.

The efficiency of a binary search is illustrated in this comparison of the number of entries in a list and the number of binary divisions required.

The order of a binary search is O(log₂N).