2.1 Binary Search Flashcards
1
Q
How does a binary search work?
A
- Calculate a mid-point in the data set
- Check if that is the item to be found
- If not:
- If the item to be found is lower than the mid point, repeat on the left half of the data set
- If the item to be found is greater than the mid point, repeat on the right half of the data set
- Repeat until the item is found or there are no items left to check
2
Q
What are some features of the binary search?
A
- Requires the data to be in order of a key field
- More efficient than a linear search on average