2.1 Binary Search

Question 1

How does a binary search work?

Answer 1

• 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

Question 2

What are some features of the binary search?

Answer 2

• Requires the data to be in order of a key field
• More efficient than a linear search on average