2.3.4 Searching Algorithms Flashcards
1
Q
Which searching algorithm requires data to be sorted?
A
Binary search
2
Q
What is the time complexity of binary search?
A
O(log n)
3
Q
What is the time complexity of linear search?
A
O(n)
4
Q
Outline the stages of a binary search.
A
Compare the middle element with item to be found
If not found, move to left half (smaller) or right half (greater)
Repeat until found or no more items to search
5
Q
Outline the stages of a linear search.
A
First item examined
If not found, next item examined
Repeated until found or end of list reached
6
Q
What data sets does linear search work best for?
A
Unordered, small data sets
7
Q
What data sets does binary search work best for?
A
Ordered, large data sets