13 GB 35 49 62 66 80 pointers from each of the next stage By

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. yak

Solution

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