Sequential
Direct Lookup
Binary
Big-O
Miscellaneous
100
What is one advantage of a sequential search?
You do not have to have your data in order.
100
What is one advantage of using a direct lookup?
The target is always found in one operation
100
What three values always need to be known in a binary search?
Low, mid & high
100
The order of complexity for a direct lookup is
O(1)
100
Which lookup strategy always finds a target with one operation?
Direct lookup
200
What is one major disadvantage of a sequential search?
You may have to search the entire array to find if the target is there
200
What is the disadvantage of using a direct lookup?
It has limited use because the target must be an array index value.
200
Why is a binary search called “binary”?
Because you are always splitting the search domain in ½
200
The order of complexity for a sequential search is
O(n)
200
Which lookup strategy requires a sorted array?
Binary search
300
When using a sequential search, when can you determine that the target is not found?
When you’ve reached the end of the array
300
Give an example when direct lookup can be used?
ID numbers range from 0-99 and scores are entered into an array based on this ID. (answers will vary)
300
How is mid calculated?
(high + low) /2
300
The order of complexity for a binary search is
O(log2n)
300
If the mid value is less than the target, what value is assigned to low?
mid +1
400
What is the worst case scenario for finding the target in a sequential search?
n, the number of items in the array
400
What is always the maximum number of operations with a direct lookup?
1
400
What is the initial value of low?
0
400
What scenario is used to calculate the order of complexity?
Worst case
400
If the mid value is greater than the target what value is assigned to high?
mid-1
500
What is the average case scenario for a sequential search?
n/2 comparisons
500
What is the average number of operations with a direct lookup?
1
500
What is the initial value of high?
n-1
500
In addition to order of complexity, what else must be considered when deciding what type of search to use?
List requirements (is the list sorted, it is set up to do a direct lookup?)
500
What is the search domain?
The area that possibly contains the target.
M
e
n
u