Q. Consider a guessing problem, where you try to guess a secret positive integer in the range 1 to . Use the divide and conquer approach to design an algorithm GUESS that takes n as a parameter and attempts to find the secret by calling the helper CHECK (shown below) to check if your guess is correct (returns 0), less than the secret (returns -1) or greater than the secret (returns +1). Your algorithm must make as few guesses as possible. Write the pseudocode for GUESSRANGE(p, r). Derive the recurrence function () for the running time and provide asymptoticboundfor(). AssumeCHECK(p)=(1). CHECK(p)

1 if p == secret return 0

2 if p < secret return -1

3 if p > secret return 1

GUESS(n) GUESSRANGE(1, n) // hint, use a helper algorithm GUESSRANGE(p, r)

GUESSRANGE(p, r)