二分查找看似简单，实际要一次AC如果不刻意练习还是很难。我把二分查找的各种情况和各种写法总结一下，类似茴字的四种写法。

基本二分查找

先上代码。

public int search(int[] nums, int target) {
    int n = nums.length;
    int left = 0, right = n - 1;
    while (right >= left) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

这里注意，首次right的取值是数组长度减一，这样做是根据我们的Loop invariant确定的。

Loop Invariant: 如果数组nums存在一个目标值target,那么target一定在nums[left, right](左闭右闭)中。
Initialization: 开始时left指向数组中第一个元素，right指向数组最后一个元素，显然成立。
Maintainance: 当nums[mid] > target时，target在nums[left, mid - 1]中，当nums[mid] < target时，target在nums[mid + 1, right]中。
Termination: 当循环终止时，有两种情况。情况1是在内层循环终止，也就是target==nums[mid]，在数组中找到了target。情况2是在外层判断后终止，也就是right < left，也就是数组的左右下标穿越，搜索空间为空，target没找到。

变式 LeetCode 35. Search Insert Position

先上代码。

public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    int left = 0, right = n - 1;
    while (right >= left) {
        int mid = left + (right- left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}

这一题目是二分查找的基本应用。由于给出的数组中没有重复，所以当在数组中找到大小为target的元素时，返回当前位置即可。没有找到就继续搜索。当循环结束且没有找到大小为target的元素时，说明left - right == 1。若越界由于left增大导致，说明在上次循环中nums[mid] < target。若越界由于right减小导致，说明上次循环中nums[mid] > target。综合考虑，当前left的位置就是应该插入新的target的位置。

变式 LeetCode 374. Guess Number Higher or Lower

先上代码。

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

在有了之前的铺垫之后，这个题目就非常简单了。

总结二分查找方便默写的几个要素：

left和right初始化时用0和n - 1，也就是右下标是不会向右越界的。
while循环的条件是left <= right，也就是包括相等的情况。
三个if的分支分别是nums[mid] == target，nums[mid] < target和nums[mid] > target，对应的操作分别是返回mid，left = mid + 1和right = mid - 1，left和right的操作具有对称性。

变式 LeetCode 278. First Bad Version

上代码。

public int firstBadVersion(int n) {
    int left = 0, right = n - 1;
    while (right >= left) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid + 1)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left + 1;
}

熟悉了之前的几个要点后直接写这个题目就可以秒AC。

变式 LeetCode 34. Search for a Range

先上代码。

public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int[] result = {-1, -1};
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left == nums.length || nums[left] != target) {
            return result;
        }
        result[0] = left;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        result[1] = right;
        return result;
    }

我们做了两次二分查找。第一次二分查找，目的是找到数组中最左边等于target的元素的位置，有两个可能的结果。第一种是在数组中找到了target，那么left指向的元素就是位于数组最左侧的等于target的元素。第二种结果是在数组中没有找到target，那么进一步可以细分两种可能性。一种是left已经越界，另一种是left没有越界，但是left指向的元素不等于target。这两种情况我们都让程序直接返回{-1, -1}。

完成第一次搜索后我们对剩下的数组进行搜索，以寻找数组中等于target的最右侧元素。由于已经确定剩余数组中起码有一个元素等于target，也就是当前left指向的元素，我们直接二分搜索剩下的数组即可。

熟练掌握之前的要点之后，这个题目也可以顺利AC。