This question comes from Levitin, A. Introduction to the Design and Analysis of Algorithms. Pearson. Exercise 5.1 Q1.
Write pseudocode for a divide-and-conquer algorithm for finding the position of the largest element in an array of n numbers.
The solution given is as below:
function MaxIndex(A, l, r)
if l = r return l
else temp1 <- MaxIndex(A, l, (l+r)/2 )
temp2 <- MaxIndex(A, (l+r)/2+1, r)
if A[temp1] >= A[temp2]
return temp1
else return temp2
However, I meet some problem when I use a random example to understand this algorithm
For example, I have an array A[20, 10, 30, 15,6] at position 0 to 4
function MaxIndex (A[.], l=0, r=4)
if l=r return l // pass
else temp1 <- MaxIndex(A, l=0, (l+r)/2=(0+4)/2=2 ) // So MaxIndex (A, 0, 2)
temp2 <- MaxIndex(A, ((l+r)/2)+1=((0+4)/2)+1 =3, r=4) // So MaxIndex(A,3,4)
if A[temp1] >= A[temp2]
return temp1
else return temp2
then
function MaxIndex (A[.], l=0, r=2)
if l=r return l // pass
else temp1_1 <- MaxIndex(A, l=0, (l+r)/2=(0+2)/2=1) // So MaxIndex (A, 0, 1)
temp1_2 <- MaxIndex(A, ((l+r)/2)+1=((0+2)/2)+1 =2, r=2) // So MaxIndex(A,2,2)
if A[temp1_1] >= A[temp1_2]
return temp1_1
else return temp1_2
then
function MaxIndex (A[.], l=0, r=1)
if l=r return l // pass
else temp1_1_1 <- MaxIndex(A, l=0, (l+r)/2=(0+1)/2=0.5) // So MaxIndex (A, 0, 0.5)?????????
temp1_1_2 <- MaxIndex(A, ((l+r)/2)+1=((0+1)/2)+1 =1.5, r=1) // So MaxIndex(A,1.5,1)??????????
if A[temp1_1] >= A[temp1_2]
return temp1_1
else return temp1_2
I feel like I cannot move any further since then. Maybe my understanding about apply this algorithm is wrong. Should I think by default, when either j or i is not an integer, round down to the nearest integer? And when ((1+r)/2)+1 > r, I will keep r value instead?