Binary Search

A binary search can only be carried out on an ordered array (numerical or alphabetical) and while more performant is significantly more complex:

The binary seach starts at the middle value, comparing that value to the on that is being searched for. If it is the correct value the search is complete, if not the algorithm determines if the value being searched for is less than or greater than the middle value. The half of the array which the value cannot be in is then discarded along with the middle value. The new middle value is compared and these steps are repeated.

Using a binary search in the example above allowed us to find our desired value in 2 iterations (repeats) of the algorithm. If we were to use a linear search it would have taken 8 iterations! However we could not have ran a binary search on a similar unordered array. Providing an array is in order a binary search will be the most efficent search algorithm available for us to use.


Included in the following specifications:
Edexcel GCSE Computer Science
OCR GCSE Computer Science