Given a API guess(int num) which will return three possible results (0 – you guess right, -1 my answer lower, and 1 my answer higher), your task is to find the the number between 1 to n – implement the guessNumber(int n) function.
Since the number from 1 to n is sorted – continious, we can use binary search O(logN) to find the answer.
Each iteration in binary search, we invoke the guess API and narrow down the search range to half (drop another half) if the middle number is not the answer.
We can implement the binary search using recursion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // Forward declaration of guess API. // @param num, your guess // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); class Solution { public: int guessNumber(int n) { return guessNumber(1, n); } private: int guessNumber(int low, int high) { int mid = low + (high - low) / 2; int x = guess(mid); if (x == 0) return mid; if (x == -1) return guessNumber(low, mid - 1); return guessNumber(mid + 1, high); } }; |
// Forward declaration of guess API. // @param num, your guess // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); class Solution { public: int guessNumber(int n) { return guessNumber(1, n); } private: int guessNumber(int low, int high) { int mid = low + (high - low) / 2; int x = guess(mid); if (x == 0) return mid; if (x == -1) return guessNumber(low, mid - 1); return guessNumber(mid + 1, high); } };
It is also very simple to implement the binary search algorithm using the iterative manner as long as we halve the search range after comparing the middle number with the target number.
THe recursive binary search implementation is easier to write, and the compiler will generate the call stacks – if the average search depth e.g. logN is large – stack may overflow.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // Forward declaration of guess API. // @param num, your guess // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); class Solution { public: int guessNumber(int n) { int low = 1; int high = n; while (low <= high) { int mid = low + (high - low) / 2; // avoid integer overflow switch(guess(mid)) { case 0: return mid; case -1: high = mid - 1; break; case 1: low = mid + 1; break; } } return -1; // indicate the number is not in the range. (NOT FOUND) } }; |
// Forward declaration of guess API. // @param num, your guess // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); class Solution { public: int guessNumber(int n) { int low = 1; int high = n; while (low <= high) { int mid = low + (high - low) / 2; // avoid integer overflow switch(guess(mid)) { case 0: return mid; case -1: high = mid - 1; break; case 1: low = mid + 1; break; } } return -1; // indicate the number is not in the range. (NOT FOUND) } };
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Simple xargs Batch Implementation for Windows
Next Post: The Array Unique Function in Javascript - Remove Duplicates in Javascript Array