2.3.1 Searching algorithms

Question 1

What are the two searching algorithms?

Answer 1

• Binary search
• Linear search

Question 2

Explain binary search

Answer 2

• DIvide and conquer
• List must be sorted
• Looks at middle element
• Looks if desired element is larger or greater
• Undesired side is discarded
• Repeat until element is found

Question 3

What is the time and space complexity for binary search

Answer 3

• Time complexity: O(log n)
• Space complexity: O(1)

Question 4

Explain linear search

Answer 4

• Look at first item
• Is it desired element
• If not look at next item
• Repeat until desired element found

Question 5

What is the time and space complexity of linear search?

Answer 5

• Time complexity: O(n)
• Space complexity: O(1)