关于二分法小知识

题目1：搜索插入位置

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

题目2：第一个错误的版本

public class Solution extends VersionControl {public int firstBadVersion(int n) {int left = 1, right = n;while(left <= right){int mid = left + (right - left) / 2;if(isBadVersion(mid)){right = mid - 1;}else{left = mid + 1;}}return left;}
}

tips:

int mid = left + (right - left) / 2;很关键
如果是 int mid = (right + left) / 2;可能会发生整型溢出