Guess Number Game

很简单的一道题，二分查找最基础的理解。

一开始没有注意到每次要mid + 1和 mid - 1，造成了死循环，另外这种题就不要递归了吧。还是quicksort类的while循环不容易出错。

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        // Write your code here
        int l = 1;
        int r = n;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (guess(mid) == 0) return mid;
            if (guess(mid) == 1) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return 0;
    }
}

Search for a Range

二分查找基础的微小变形结合，变形一是找最小下标，二是找最大下标。

不要偷懒，复制代码容易出错。

还是一样的方法，用while循环可以解决。一直找，找到target的时候继续向左或者向右去找。这样可以找到最大或者最小下标。

初始化为-1可以满足题目的要求，找不到都返回-1。

public class Solution {
    public int[] searchRange(int[] A, int target) {
        // write your code here
        int[] res = new int[2];
        if (A == null || A.length == 0) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        int ansl = -1;
        int ansr = -1;
        int l = 0;
        int r = A.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (A[mid] > target) {
                r = mid - 1;
            }
            if (A[mid] < target) {
                l = mid + 1;
            }
            if (A[mid] == target) {
                ansl = mid;
                r = mid - 1;
            }
        }
        l = 0;
        r = A.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (A[mid] > target) {
                r = mid - 1;
            }
            if (A[mid] < target) {
                l = mid + 1;
            }
            if (A[mid] == target) {
                ansr = mid;
                l = mid + 1;
            }
        }
        res[0] = ansl;
        res[1] = ansr;
        return res;
    }
}

First Bad Version

while (start + 1 < end) 这样一种新的想法，这道题与之前不同之处在于它不是大于小于等于三种状态，而是boolean的两种状态，所以用start + 1 < end 来保证start和end指针在推移的过程中不会相遇，就像是quicksort，然后在最后处理只有两个潜在答案的情况，先是判断start再是end。

class Solution {
    public int findFirstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (SVNRepo.isBadVersion(mid)) {
                end = mid;
            } else start = mid;
        }
        if (SVNRepo.isBadVersion(start)) {
            return start;
        }
        return end;
    }
}