Binary Search
Computer Science: OCR A Level, topic 8.1.10
Binary Search
Binary search is an example of a divide-and-conquer algorithm.
The concept
- 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.
In English
- Find the middle of the dataset.
- If the middle value is greater than the target then:
- Repeat on the first half of dataset.
- If the middle value is lesser than the target then:
- Repeat on the second half of dataset.
- If the middle value is the target:
- We found it!
- Stop repeating once the size of our dataset is zero.
In pseudocode
Pros and cons of binary search
- Pros:
- Faster than linear search on a large dataset.
- Cons:
- Dataset must be sorted before starting.
Test yourself on Binary Search
Binary search is an example of what type of algorithm?
What is the main advantage of binary search?