Searching Algorithms

• What is an algorithm?

  A set of instructions to complete a task
• What is the primary task of a searching algorithm?

  To find the location of an item in a list
• Name 2 types of searching algorithm.

  Linear and Binary search
• What is the time complexity of a linear search?

  O(N)
• On what type of list can a linear search be conducted?

  Any unordered list
• What are the steps in a linear search algorithm?

  • Compare each item sequentially
  • Check if it matches the target
  • Continue until found or end of list
• Why is using a For...Next loop in a linear search considered bad practice?

  It uses definite iteration instead of indefinite
• What is the time complexity of both Do Until and For...Next loops in a linear search?

  O(N)
• What is the time complexity of a binary search?

  O(logN)
• What is a binary tree?

  An a cyclic connected graph
• How does a binary tree search differ from a binary search?

  It is conducted on a binary tree
• What is the time complexity of a binary tree search?

  O(logN)
• What are the steps in a binary tree search?

  • Start at the root
  • Compare target with node
  • Traverse left or right based on comparison
• What are the characteristics of a binary tree?

  • Acyclic
  • Connected graph
  • Each node has 0, 1, or 2 children
• What are the steps to conduct a binary search on an array?

  1. Sort the array
  2. Find the midpoint
  3. Compare target with midpoint
  4. Discard half of the array
  5. Repeat until found or empty
• How do binary searches compare to linear searches in terms of speed?

  Binary searches are much faster than linear searches