Searching algorithms Flashcards
1
Q
When to use linear search?
A
unordered list
2
Q
When to use binary search?
A
ordered list
3
Q
Define linear search
A
process sequentially through an unordered list
4
Q
Best case of linear search
A
O(1)
first element in list
5
Q
Worst case of linear search
A
O(n)
last element in list
6
Q
Define binary search
A
calculates midpoints in an ordered list of items to find the required element
7
Q
best case of binary search
A
element in the middle of the list
O(1)
8
Q
worst case of binary search
A
element is found in last comparison
O(logn + 1)
9
Q
average case of binary search
A
O(logn)
10
Q
advantages of binary search
A
- much more efficient, as it only focuses on one half of the list
- worst case is still shorter than linear worst case
11
Q
disadvantages of binary search
A
only works on ordered lists
