Challenge: Recursion

Logic building

In order to solve part (a) of the problem, we’ll first begin by analyzing the algorithm below. After that, we’ll move on to coding implementation.

(a) Algorithm to compute $k$:

• Initialize two pointers, left and right, to the beginning and end of the array, respectively ($left = 0, right = n - 1$).
• While $left < right$:
  • Calculate the middle index: $mid = (left + right) // 2$

...