Consider the following list: 5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110
ID: 3693220 • Letter: C
Question
Consider the following list: 5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110 Using the binary search, how many comparisons are required to determine whether following items are in the list or not Show the values of first, last, and middle and number of comparisons after each iteration of the loop. 32 20 Recall the insertion sort algorithm as discussed in this chapter. Assume following list of keys: 30, 20, 35, 27, 96, 82, 60, 48, 75, 5, 80 Exactly how many key comparisons are executed to sort this list using insertion sc Show the values and the number of comparisons after each iteration for the loop. What is the output of the following C + + codeExplanation / Answer
1)List={5,12,25,32,38,46,58,62,85,90,97,105,110}
a) for 32:
iter 1: first=5 ,last= 110, middle=58
comparisions=1
iter 2: first=5 ,last= 58, middle=32
comparisions=2
32 is found.
b) for 20:
iter 1: first=5 ,last= 110, middle=58
comparisions=1
iter 2: first=5 ,last= 58, middle=32
comparisions=2
iter 3: first=5 ,last= 32, middle=25
comparisions=3
iter 4: first=5 ,last= 25, middle=12
comparisions=4
search completed but 20 is not found.
2) L={30,20,35,27,96,82,60,48,75,5,80}
iter 1: {20,30,35,27,96,82,60,48,75,5,80}
comparisons:1
iter 2: {20,30,35,27,96,82,60,48,75,5,80}
comparisons:3
iter 3: {20,27,30,35,96,82,60,48,75,5,80}
comparisons:6
iter 4: {20,27,30,35,96,82,60,48,75,5,80}
comparisons:10
iter 5: {20,27,30,35,82,96,60,48,75,5,80}
comparisons:15
iter 6: {20,27,30,35,60,82,96,48,75,5,80}
comparisons:20
iter 7: {20,27,30,35,48,60,82,96,75,5,80}
comparisons:25
iter 8: {20,27,30,35,48,60,75,82,96,5,80}
comparisons:32
iter 9: {5,20,27,30,35,48,60,75,82,96,80}
comparisons:33
iter 10: {5,20,27,30,35,48,60,75,80,82,96}
comparisons:42
3) 5 3
is the output.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.