Apply algorithm 4.1.2 in P.140 with T=63, n=12 and A=(3,5,8,8,9,16,29,41,50,63,64,67). Draw the corresponding walkthrough as shown in P.140. Algorithm 4.1.2: Binary SearchBeginp - 1;q + n;Repeatj- [(p + q) /2];If (A[j] < T) Thenp+j+1;End;If (A[j] > T) Thenq +j- 1;End;Until ( (A[j] = T) Or (p > q) );If (A[j] = T) Then Output("T is A[", j, "]");Else Output("T is not in A");End;End.Walkthrough with n = 12 and A = (3, 5, 8, 8, 9, 16, 29, 41, 50, 63, 64, 67)/| A[1] = 3,/| A[7] = 29, A[8] = 41, A[9] = 50, A[10] = 63, A[11] = 64, &A[6] = 16,A[12] = 67A[2] = 5,A[3] = 8,A[4] = 8,A[5] = 9,If T = 9, thenA[j]relationoutput161216T If T = 99, thenA[j]relationoutput1216A[j] < T91250A[j] < T10111264A[j] < T12121267A[j] < T1312T is not in A/| T lies beyond A„-// When n = 12, is the first probe always at A[6] and the second, either at A[3] or/| A[9]?//// In general:// Is this algorithm sure to terminate?// How many iterations of the loop could there be?// Is this algorithm correct? If T is in A is the algorithm guaranteed to find it?// If T is not in A, must p eventually become larger than q?Suppose the sublist we’re searching is from A[p] up to A[q] of length k and weprobe unsuccessfully at A[j]:// k = q – p+1.A[p]...Alj – 1]A[] Alj+1]...A[q] -klk2If A[j] > T, then we will search from A[p] up to Alj – 1] of length kl = j – p.If A[j] < T, then we will search from A[j + 1] up to A[q] of length k2 = q – j.We would like kl and k2 to be equal, but if that's not possible (because q – p isodd), let's consistently make kl the smaller value.// How should we choose j so that kl <= k2 and k2 is as small as possible?To make k2 = q – j as small as possible, we need to make j as large as possible.We wantkl + k2 <= k2+k2,q - p <= 2(q –j)2j <= 2q – (q – p) = q+p.that is,= 29 – 2jorThe largest integer j <= (q+p)/2 is [(q + p)/2], and this is the j-value used in thealgorithm.

Here is the solution:-The corresponding walkthrough is as follows: Walkthrough with n=12, A=(3,5,8,8,9,16,29,41,50,63,64,67) and T=63// A[1]=3, A[2]=5, A[3]=8, A[4]=8, A[5]=9, A[6]=16,// A[7]=29, A[8]=41, A[9]=50, A[10]=63, A[11]=64, & A[12]=67 p j q A[j] relation output1 6 12 16 A[j]<T -7 9 12 50 A[j]<T -10 11 12 64 A[j]>T -10 10 10 63 A[j]=T T is A[10]