Java Solution using Binary Search (Iterative)


  • 0
    Y

    Since number from start to end are sorted, we think of binary search approach to solve this problem. Each time we iteratively compare the middle number (marked as mid = start + (end - start)/2) with the picked up number using guess(num) function, then update the lower bound or upper bound of numbers from comparison results. The following is the solution using binary search in iterative approach. Since the search scope halves each time, the time complexity of the algorithm is log(n). The space complexity is O(1) since only fixed variables are used.

    public int guessNumber(int n) {
        int start = 1, end = n;
        while(start < end) {
            int mid = start + (end - start)/2;
            int result = guess(mid);
            if(result == 0) {
                return mid;
            }
            else if(result == -1) {
                end = mid - 1;
            }
            else if(result == 1) {
                start = mid + 1;
            }
        }
        return start;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.