Searching algorithms

Question 1

When to use linear search?

Answer 1

unordered list

Question 2

When to use binary search?

Answer 2

ordered list

Question 3

Define linear search

Answer 3

process sequentially through an unordered list

Question 4

Best case of linear search

Answer 4

O(1)

first element in list

Question 5

Worst case of linear search

Answer 5

O(n)

last element in list

Question 6

Define binary search

Answer 6

calculates midpoints in an ordered list of items to find the required element

Question 7

best case of binary search

Answer 7

element in the middle of the list

O(1)

Question 8

worst case of binary search

Answer 8

element is found in last comparison

O(logn + 1)

Question 9

average case of binary search

Answer 9

O(logn)

Question 10

advantages of binary search

Answer 10

• much more efficient, as it only focuses on one half of the list
• worst case is still shorter than linear worst case

Question 11

disadvantages of binary search

Answer 11

only works on ordered lists