704. 二分查找

public int search(int[] nums, int target) {
	int left = 0;
    int right = nums.length - 1; //别忘了减一
    
    while(left<=right){
        int mid = (right-left)/2+left;
        int num = nums[mid];
        if(num==target){return mid;}
        else if(num<target){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    
    return -1;
}

1. 一开始我写的是 int mid=nums.length/2：为什么不能这么写？
   • 因为nums.length/2是固定的一个常数，不会随着子数组左右边界缩小而缩小！
2. int mid = (right-left)/2+left;：为什么不写成 int mid = (right+left)/2;？
   • 因为如果right, left很大，那么right+left就会正溢出，(right-left)/2+left 这个式子等价于后者，但可以防止溢出；
3. while(left<=right)：

   • 没有使用递归调用search(nums, target)的方法，而是用一个while循环来迭代，因为这个函数的参数是整个数组nums而不是左右边界left, right，如果递归的话还需要创建两个子数组，耗费时间空间，所以直接采取迭代形式；

   • (left<=right) 这个二分终止条件一定要记住！