Binary Search

• Advantages and Disadvantages of Binary search:

  +

  • Efficient - Does not need to search every single element/uses divide and conquer, suitable for large amounts of data

  -

  • Data has to be in order
• Difference between binary and linear search:

  • Binary search discards half data at each step
  • Linear search discards one data item at each step / each item in turn
• Steps of a Binary search:

  • Find the middle point of the system by N/2
  • Compares it to the middle value
  • If it is the middle value then return True
  • If not compare if it is larger or smaller then the middle value and update the pointers as necessary
  • Repeat until item is found or the end of the list is reached
  • Return False if item is not found
• Code for binary search in python:

  • Remember it is easy if you know the algorithm