二分查找（折半查找）

1、寻找一个数

二分查找的通用模板如下：

  1. public int binarySearch(int[] nums, int target) {
  2.     int left = 0;
  3.     int right = nums.length - 1;
  5.     while(left <= right) {    
  7.         /** 注意！
  8.          * 这里采用 int mid = (right - left) / 2 + left; 是为了防止溢出
  9.          * 使用 int mid = (right + left) / 2; 得出来的结果值是一样的
  10.          **/
  11.         int mid = (right - left) / 2 + left;    //取中间数
  13.         if (nums[mid] == target) {    
  14.             return target;
  15.         }else if (nums[mid] < target) {
  16.             left = mid + 1;    
  17.         }else if (nums[mid] > target) {
  18.             right = mid - 1;    
  19.         }
  20.     }
  21.     return ...;
  22. }

2、寻找左侧边界

3、寻找右侧边界