6.2 Searching Algorithms Flashcards
1
Q
Give 2 searching algorithms for lists or arrays
A
Binary
Linear
2
Q
Binary search requirements
A
Must have a sorted list
3
Q
How does a binary search work?
A
The middle item of a list is first checked
If the item is greater than the node your are looking for, it will loom on the left side, otherwise on the right side.
This process keeps happening untill the searching node becomes a midpoint
4
Q
How does a liner search work?
A
Each item is checked against the search item in order (ie iteration, but list order does not matter)
5
Q
In a list of 2^n items, what will be the maximum items you will have to search for in a binary search?
A
n+1
