二分查找

代码模板

/**
* 二分查找模板
*/
 public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int mid;
        while (left < right) {
           mid = left + (right - left) / 2; // 防止计算时溢出
            if(条件){
                right = mid-1;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }

注意事项

二分查找使用：

• mid = left + (right – left) / 2
• mid = ((right – left) >> 1) + left
  
  
  避免（left+right）出现溢出