Standard Binary Search


  • 0
    Y

    Haven't used binary search for so long that I almost forget it completely.
    The tricky part is to use (hi-lo)/2 + lo to compute mid instead of (lo + hi) / 2, because the later can cause overflow and makes the algorithm work incorrectly.

    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int lo = 0, hi = n;
            while (lo <= hi) {
                int mid = (hi - lo) / 2 + lo;
                if (guess(mid) == -1) {
                    hi = mid - 1;
                } else if (guess(mid) == 1) {
                    lo = mid + 1;
                } else if (guess(mid) == 0) {
                    return mid;
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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