Software Engineering 487

Consider a guessing game in which you attempt to guess a secret positive integer in the range 1 to n. 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 T(n) for the running time and provide asymptotic bound for T(n). Assume CHECK(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)