二分算法

描述

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1

样例  1:
	输入:[1,4,4,5,7,7,8,9,9,10]，1
	输出: 0
	
	样例解释: 
	第一次出现在第0个位置。

样例 2:
	输入: [1, 2, 3, 3, 4, 5, 10]，3
	输出: 2
	
	样例解释: 
	第一次出现在第2个位置
	
样例 3:
	输入: [1, 2, 3, 3, 4, 5, 10]，6
	输出: -1
	
	样例解释: 
	没有出现过6， 返回-1

我们先看下基础的二分代码：

num[]
left = 0, right = nums.length /* + 1          ……1.*/
while (left < right /*left <= right           ……2.*/) {
	middle = (left + right) / 2
	if (nums[middle] == target) {
		return middle;
	} else if (nums[middle] > target) {
		right = middle /* - 1 ??       ……3.*/
	} else {
		left = middle  /* + 1 ??       ……4.*/
	}
}

二分的思想虽然比较简单：选取中间值，中间值与目标值作比较，根据比较结果舍弃一半的操作 但是，它的代码却有比较多的坑

1. 区间的选择：right 的值我们可以选择 right = nums.length 也可以选择 nums.length - 1; 这两种不同选择直接影响的是 while 的判断
2. 如果第一步选择的是 nums.length, 也就说明 right 的值是个“越界位”，我们不能选择，所以此时对于应的是 left < right，[left, right); 如果第一步选择的是 nums.length 那么意味着 right 值也是可以 check 的，所以此时可以是 left <= right, [left, right];

middle 位对应的值不等于 target，middle 的值应该如何做下一步的选择？？

3. middle 需不需要 - 1 ？？
4. middle 需不需要 + 1 ？？

如果 middle 不进行 +1或者-1的话，我们考虑一种情况： left + 1 == right时，middle = (left + left + 1) / 2 = left 如果 nums[middle] 不等于 target，那么就会陷入死循环。

所以我们最终代码如下：

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

704. 二分查找