Binary Search

Computer Science: OCR GCSE, topic 2.1.10

Binary search is a type of algorithm known as a divide-and-conquer algorithm.

If you try to find a certain page in a book, it's unlikely that you check every page on the way.
You are more likely to split the book in two, then see if the page you need is before or after the split, and repeat.
This is the concept behind the binary search.
Data must be in a specific order. Example: lowest to highest, A->Z

Find a certain value within a range of values. Find the middle of the dataset.
If the middle value is greater than the target then:
Repeat on the first half of dataset. You can discard the second half of the dataset as you know all of these values are greater than the value you are trying to find.
If the middle value is lesser than the target then:
Repeat on the second half of dataset. This is the second half of the dataset after 50% was already removed when the first middle was found.
If the middle value is the target:
We found it!
Stop repeating once the size of our dataset is zero.

Test yourself on Binary Search