2.3.4 Searching Algorithms

• Binary Search

  • only works on sorted data
  • Efficient - divide and conquer
  • Time complexity O (log n )
• 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
• Binary vs Linear

  • Binary search is more efficient since half of the list is discarded at each step, linear only one is removed
  • Binary searches requires list to be in order whereas linear doesn't
• Binary Search

  
• Linear Search:

  • Start from the beginning of the data set
  • Compare the search item with the first value
  • Search sequentially with the next value
  • Repeat until search item is found and then stop
  • Or return False if item is not found
  • Time complexity O(n)
• Linear Search

  • most basic searching algorithm
  • You can think of it as going along a bookshelf one by one until you come across the book you’re looking for
  • Easy to implement
  • Inefficient
  • Data does not have to be in order