Searching¶
Q) Linear Search: Counting numbers analyzed¶
Given the following sorted array of integers, how many numbers in the array will be analyzed by a Linear Search algorithm to search for the number 21?
Use the algorithm described in the notes. Note that the data values are shown with the index above to make your life easier!
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Data: 1, 5, 8, 9, 11, 15, 16, 19, 20, 21, 29, 30, 35, 41, 44, 49
a) Between 0 and 4 elements
b) Between 5 and 9 elements
c) Between 10 and 12 elements
d) Between 13 and 16 elements
Q) Binary Search: Counting numbers analyzed¶
Given the following sorted array of integers, how many numbers in the array will be analyzed by a Binary Search algorithm to search for the number 21?
Use the algorithm described in the notes. Note that the data values are shown with the index above to make your life easier!
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Data: 1, 5, 8, 9, 11, 15, 16, 19, 20, 21, 29, 30, 35, 41, 44, 49
a) 2 elements
b) 3 elements
c) 4 elements
d) 5 elements
Q) Fastest Search on this data¶
Consider the following data:
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Data: 2, 5, 1, 9, 53, 51, 0, -1, 95, 1, 1, 35, 5, 2, 1, 51
What is the fastest search algorithm that we can apply to find an element in the array:
a) Linear search.
b) Binary search.
c) Neither algorithm works for this data.
d) Both algorithms are equally fast with this data set.
Answers¶
1 = c) Between 10 and 12 elements (actually 10: 0 through 9)
2 = b) 3 elements
3 = a) Linear search; the data is un-sorted.