13 GB) 35 49 62 (66) 80 pointers from each of the next stage By the same reasoni
ID: 3799283 • Letter: 1
Question
13 GB) 35 49 62 (66) 80 pointers from each of the next stage By the same reasoning, the sub at elements to the node 49 The resulting structure is usually drawn with rigid pointers, giving it an u down tree-like shape: 62 It is called a binary search tree and is a special kind of bina tree, which is the structure studied in the rest of this chapter. Exercises 12.1 Exercises 1-5 use the following array critter: 0 1 3 4 5 7 critter[i] auk bat T cow T eel elk T fox T gnu pig rat Give the indices of the elements of critter in the order that the c examined during a binary search for 1. gnu 2. eel 3. fly 4, ant 5. yakExplanation / Answer
int BinarySearch(String A[], int F, int L, String value)
{ int m;
while( F <= L )
{
m = F + (L-l)/2;
if( A[m] == value ) // if A[m]==key then return m
return m;
if( A[m] < value ) // second comparison
F = m + 1;
else
L = m - 1;
}
return -1;
}
===================================
0
1
2
3
4
5
6
7
8
Critters
auk
bat
cow
eel
elk
fox
gnu
pig
rat
F=0 and L=8
mid= (0+8)/2 =4
critters[4] != gnu (critters[4]< gnu)
F =mid+1 =5, L=8
mid= (5+8)/2 =6
critters[6] == gnu
so gnu would go through the indices 4 -> 6
2 ) eel
F=0 and L=8
mid= (0+8)/2 =4
critters[4] != eel (critters[4]> eel)
L =mid-1 =3, F=0
Mid= (0+3)/2 =1
critters[1] != eel (critters[1]< eel)
F=mid+1=2, L=3
Mid=(2+3)/2 =2
critters[2] != eel (critters[1]< eel)
F=3, L=3 , Mid=3
critters[3]==eel
so eel would go through the indices 4 -> 1 -> 2 -> 3
3) fly
F=0 and L=8
mid= (0+8)/2 =4
critters[4] != fly (critters[4]< fly)
F =mid+1 =5, L=8
mid= (5+8)/2 =6
critters[6] !=fly (critters[6]> fly)
F=5,L=5
Mid =5
Critters[5] !=fly
exit
so fly would go through the indices 4 -> 6 -> 5
4) ant
F=0 and L=8
mid= (0+8)/2 =4
critters[4] != ant (critters[4]> ant)
L =mid-1 =3, F=0
Mid= (0+3)/2 =1
critters[1] != ant (critters[1]> ant)
L=mid-1=0, F=0
Mid=(0+0)/2 =0
critters[0] != ant
exit
so ant would go through the indices 4 -> 1 -> 0
5) yak
F=0 and L=8
mid= (0+8)/2 =4
critters[4] != yak (critters[4]< yak)
F =mid+1 =5, L=8
mid= (5+8)/2 =6
critters[6] !=yak (critters[6]< yak)
F=7,L=8
Mid =7
Critters[7] !=yak
F=8,L=8
Mid=8
Critters[8] !=yak
exit
so yak would go through the indices 4 -> 6 -> 7->8
---------------------------------------------------------------------------------------------
If you have any query, please feel free to ask.
Thanks a lot.
0
1
2
3
4
5
6
7
8
Critters
auk
bat
cow
eel
elk
fox
gnu
pig
rat
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.