2.3.1 Searching Algorithms

Question 1

Which search algorithm requires data to be sorted before perfoming the algorithm?

Answer 1

Binary Search

Question 2

Perform linear search for 9 :
[ 1, 2, 3, 5, 7, 9, 11, 12 ]

Answer 2

Check till find 9 and then terminates.

Question 3

What is the time complexity of Binary Search?

Answer 3

O (log n)

Very efficient for more items

Question 4

Perform Binary search for 6 :
[ 1, 3, 6, 7, 9, 12, 13 ]

Answer 4

• Goes to midpoint, 7
• 6 < 7 Therefore goes to the left of 7
• Array is now [ 1, 3, 6 ]
• Goes to midpoint, 3
• 6 > 3 Therefore goes to the right of 3
• Array is now [ 6 ]
• 6 = 6 Therefore 6 is found and Algorithm terminates

Question 5

Which search algorithm has a time complexity of O(n)?

Answer 5

Linear Search

Question 6

Which sorting algorithm is the most time efficient ; Bubble or Merge

Answer 6

Merge Sort

Merge is O (n log n) Bubble has a best case O(1) and a worst of O(n^2)

Question 7

Which sorting algorithm uses divide and conquer?

Answer 7

Merge Sort

Question 8

Time Complexity of Bubble Sort?

Answer 8

O(1) - Best case
O(n^2) - Worst case

Question 9

Time complexity of Merge Sort?

Answer 9

O ( n log n)

Question 10

Sort into ascending using bubble sort :
4 3 5 7 6

Answer 10

1. [ 4 3 5 7 6 ]
2. [(3 4) 5 7 6]
3. [3 4 5 (6 7)]
4. [ 3 4 5 6 7 ]

brackets show the switches remember that it will go through fully after

Question 11

Sort in alphabetical order using merge sort:
Tom Sue Jack Bill Ada

Answer 11

• Separate into 3 and 2
• Tom Sue Jack → Jack Sue Tom
• Bill Ada → Ada Bill
• Combine to get Ada Bill Jack Sue Tom