below is a recursive implementation of binary search written in C. Every time th
ID: 668180 • Letter: B
Question
below is a recursive implementation of binary search written in C. Every time the function is called, the first thing it does is print TICK
For each of the following values of n, determine exactly how many TICKs are printed by by the function under the assumption that the value being searched for is larger than all elements in the sorted array.
n = 1, 2, 5, 10, 20, 40, 80, 160, 320, 640, 1280
Note: you are expected to determine the answers “manually” – not by coding up the algorithm and running it (though you could confirm answers this way).
Explanation / Answer
Binary search is usually of worst case efficiency O(log n).
As you said you are going to search always an element that is larger than all the elements in the list, the number of ticks printed for your given values of n are as follows:
n = 1.
bsearch(a,0,0,key)
TICK printed.
mid = (0+0)/2. /*0*/
bsearch(a,1,0,key)
TICK printed.
if(hi < lo) /*Condition Satisfies.*/
return 0.
-----------------------------------------------------------
TICK printed 2 times.
-----------------------------------------------------------
n=2.
bsearch(a,0,1,key)
TICK printed.
mid = (0+1)/2 /*0*/
bsearch(a,1,1,key)
TICK printed.
mid=(1+1)/2 /*1*/
bsearch(a,2,1,key)
TICK printed.
if(hi < lo) /*Condition Satisfies.*/
return 0.
-----------------------------------------------------------
TICK printed 3 times.
-----------------------------------------------------------
n=5.
bsearch(a,0,4,key)
TICK printed.
mid = (0+4)/2 /*2*/
bsearch(a,3,4,key)
TICK printed.
mid = (3+4)/2 /*3*/
bsearch(a,4,4,key)
TICK printed.
mid = (4+4)/2 /*4*/
bsearch(a,5,4,key)
TICK printed.
if(hi < lo) /*Condition Satisfies.*/
return 0.
-----------------------------------------------------------
TICK printed 4 times.
-----------------------------------------------------------
n=10.
bsearch(a,0,9,key)
TICK printed.
mid = (0+9)/2. /*4*/
bsearch(a,5,9,key)
TICK printed.
mid = (5+9)/2 /*7*/
bsearch(a,8,9,key)
TICK printed.
mid = (8+9)/2 /*8*/
bsearch(a,9,9,key)
TICK printed.
mid = (9+9)/2. /*9*/
bsearch(a,10,9,key)
TICK printed.
if(hi < lo) /*Condition Satisfies.*/
return 0.
-----------------------------------------------------------
TICK printed 5 times.
-----------------------------------------------------------
n=20.
bsearch(a,0,19,key)
TICK printed.
mid = 9
bsearch(a,10,19,key)
TICK printed.
mid = 14
bsearch(a,15,19,key)
TICK printed.
mid = 17
bsearch(a,18,19,key)
TICK printed.
mid = 18
bsearch(a,19,19,key)
TICK printed.
mid = 19
bsearch(a,20,19,key)
TICK printed.
if(hi < lo) /*Condition Satisfies.*/
return 0.
-----------------------------------------------------------
TICK printed 6 times.
-----------------------------------------------------------
Proceeded this way:
For 40 7 ticks will be printed.
For 80 8 ticks will be printed.
For 160 9 ticks will be printed.
For 320 10 ticks will be printed.
For 640 11 ticks will be printed.
For 1280 12 ticks will be printed.
A sample of last one:
bsearch(a,0,1279,key) TICK
bsearch(a,640,1279,key) TICK
bsearch(a,960,1279,key) TICK
bsearch(a,1120,1279,key) TICK
bsearch(a,1200,1279,key) TICK
bsearch(a,1240,1279,key) TICK
bsearch(a,1260,1279,key) TICK
bsearch(a,1270,1279,key) TICK
bsearch(a,1275,1279,key) TICK
bsearch(a,1278,1279,key) TICK
bsearch(a,1279,1279,key) TICK
bsearch(a,1280,1279,key) TICK
Therefore, as you asked, the number of TICKs printed for various values of n are:
1 : 2.
2 : 3.
5 : 4.
10 : 5.
20 : 6.
40 : 7.
80 :8.
160 :9.
320 :10.
640 :11.
1280:12.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.