What value of \(q\) does PARTITION return when all elements in the array \(A[p .. r]\) have the same value? Modify PARTITION so that \(q = \lfloor (p + r) / 2 \rfloor\) when all the elements in the array \(A[p..r]\) have the same value.

When \(A[p .. r]\) contains only identical elements, PARTITION returns a value of \(r - 1\).

MODIFIED-PARTITION(\(A, p, r)\)

1  x = A[r]

2  i = p - 1

3  for j = p to r - 1:

4      if A[j] ≤ x:

5          i = i + 1

6          exchange A[i] with A[j]

7  if i == r - 1 and A[p] == A[r]:

8      return floor((p+r) / 2)

9  else:

10      exchange A[i+1] with A[r]

11      return i + 1

The logical condition on line 7 will be true when we have found all values in \(A[p .. r-1]\) to be less than or equal to \(A[r]\). If it is also the case that \(A[p]\) and \(A[r]\) are the same value, then it must be true that \(A[p..r]\) contains all equal aelements and we can simply return the midpoint. All other functionality remains intact.