2.3.4 Searching Algorithms

• What are searching algorithms used for?

  To find a specified element in data
• Why are different searching algorithms used?

  They suit particular data structures and scenarios
• What is a requirement for using binary search?

  Data must be sorted
• How does binary search determine which side of data to search?

  By finding the middle element and comparing
• What happens to the data in each iteration of binary search?

  Half of the input data is discarded
• What is the time complexity of binary search?

  O(log n)
• What is the pseudocode for binary search?

  • A = Array of data
  • x = Desired element
  • low = 0
  • high = A.length - 1
  • while low <= high:
  • mid = (low + high) / 2
  • if A[mid] == x: return mid
  • else if A[mid] > x: high = mid - 1
  • else: low = mid + 1
  • return “Not found in data”
• What is the middle position calculated in the first step of searching "Dylan"?

  4
• What do we do when the middle element is higher than the desired element?

  Discard the upper half of the data
• What is the final position returned when "Dylan" is found?

  3
• What happens when low exceeds high in the binary search process?

  The algorithm returns “Not found in data”
• How does binary search compare to linear search in efficiency?

  • Binary search is more efficient
  • It halves the search space each iteration
  • Linear search checks each element sequentially
• What is the time complexity of linear search?

  O(n)
• What is a key characteristic of linear search?

  It does not require sorted data
• What is the pseudocode for linear search?

  • A = Array of data
  • x = Desired element
  • i = 0
  • while i < A.length:
  • if A[i] == x: return i
  • else: i = i + 1
  • return “Not found in data”
• How does linear search compare to binary search in terms of efficiency?

  • Linear search is less efficient
  • It checks each element one by one
  • Binary search halves the search space
• What is the main disadvantage of linear search?

  It can be incredibly inefficient
• How does the algorithm behave when searching for "R" in the alphabet?

  It shows less efficiency than binary search
• What is the main characteristic of linear search regarding data structure?

  It can work with unsorted data
• How does the efficiency of linear search change with data size?

  It becomes slower as data size increases