Computing - Component 2, Topic 1

COMP 2 - ALGORITHMS AND SEARCH/SORT METHODS

• Algorithm: A set of instructions that logically solves a problem
• Abstraction: Obtaining the important parts of the problem and eliminating unnecessary information
• Decomposition: Breaking a large problem into smaller sub-problems, making it easier to solve
• Algorithmic Thinking: Thinking in a logical and concise way to find a solution for a problem 

SEARCH METHODS

• Binary Search: Looks for items in an ordered list 
  • List must be in order
  • Worst case scenario: Checks half of list
  • Algorithm is longer and more complex to write
    • Finds middle value 
    • If the value is found, the search will stop
    • If the value is not found, it will compare the middle item to the item it is looking for
    • If item is before the middle, it will look at that half of the list
    • If the item is after the middle, it will look at that half of the list after the middle item
    • This will repeat continuously with smaller lists until the value is found
• Linear Search: Each item in the list is checked in order
  • List does not have to be in order
  • Worst case scenario: Will check whole list
  • Algorithm is simpler to write 
    • Checks first…