普通二分

目标：从数组中寻找target，有则返回下标，没有则返回-1。

返回值范围：[-1, n-1]

终止while条件：如果不包含target，即正常退出while，则此时必有left=right+1。此时区间[left,right]不包含任何元素，返回-1。

区间缩小规则：

如果mid==target，返回mid。
如果mid>target，在[left, mid-1]找，
否则，在[mid+1,right]找。

特点：如果有多个元素=target，会返回任意一个。

public static int binarySearch(int[] arr, int target){
	int left = 0;
	int right = arr.length-1;
	while(left<=right){// 注意
	    int mid = (left+right)/2;
	    if(arr[mid]==target){
	        return mid;
	    }else if(arr[mid] >target){
	        right = mid-1;
		    }else if(arr[mid]<target){
        	left = mid+1;
    	}
	}
	return -1;
}

为什么right初始值是arr.length-1，终止while前有left=right，进而mid=right，如果right=arr.length,会越界。而且根据返回值的意义和范围，left和right需要设置成这样。

找第一个大于等于target的下标

目标：找第一个大于等于target的下标；
返回值还有一个含义：小于target的数有几个。
具体来说，如果数组里面有target，返回第一次等于target的元素下标：如果不包含target，则返回第一个大于target 的元素下标。若所有元素均小于target，返回n。

返回值范围：[0,n]

终止while条件：必有left==right。此时区间[left,right]里只有一个元素，直接返回left或right

区间缩小方法：

如果mid元素大于等于target。要找的必定是当前位置或者当前位置左边，令right=mid，即在[left,mid]之间找。
如果mid元素小于target，要找的下标必定在右边：left = mid+1，即在[mid+1, right]之间找。

// 只有4个需要注意的地方。
public static int binarySearch(int arr[], int target){
    int left = 0;
    int right = arr.length; // 注意
    while(left<right){ // 注意
        int mid = (left+right)/2;
        if(arr[mid] >= target){// 注意
            right = mid;
        }else{
            left = mid+1;
        }
    }
    return left;// 注意
}

为什么right初始值是arr.length。因为终止while前必有left<right，进而mid<right，所以不用担心越界。而且根据返回值的意义和范围，left和right需要设置成这样。

找第一个大于target的下标

目标：找第一个大于target的下标；没有大于target的元素则返回n
返回值还有一个含义：小于等于target的数有几个。

返回值范围：[0, n]

终止while条件：必有left==right。此时区间[left,right]里只有一个元素，直接返回left或right

区间缩小方法：

如果mid元素大于target。要找的必定是当前位置或当前位置左边，right=mid，即在[left,mid]之间找。
如果mid元素小于等于target，要找的下标必定在右边：left = mid+1，即在[mid+1, right]之间找。

public static int binarySearch(int arr[], int target){
    int left = 0;
    int right = arr.length;
    while(left<right){
        int mid = (left+right)/2;
        if(arr[mid] > target){// 注意
            right = mid; 
        }else{
            left = mid+1;
        }
    }
    return left;// 注意
}

找最后一个小于等于target的下标

作用：找出最后一个小于等于target的元素下标。所有元素均大于target则返回-1.

返回值范围：[-1,n-1]

分析：用上面的方法可以找第一个大于target的下标index，因此index-1对应的元素必定不大于target，index-1即为所求。
所以只需要把上面的代码最后一行改成left-1就可以了。

public static int binarySearch(int arr[], int target){
    int left = 0;
    int right = arr.length;
    while(left<right){
        int mid = (left+right)/2;
        if(arr[mid] > target){// 注意
            right = mid; 
        }else{
            left = mid+1;
        }
    }
    return left-1;// 注意
}