二分搜索结束后，数组的题目或者技巧就差不多入门了。
按照网站的做题路线。二分查找思想就是左右指针，
但是二分查找真正的坑根本就不是那个细节问题，而是在于到底要给 mid 加一还是减一，while 里到底用 <= 还是 <。所以要明确「搜索区间」
而我的烦恼一直是，二分插入排序时，left还是right才是要插入的地方。
防止溢出：int mid = left + (right - left) / 2;
对于JavaScript，得到mid带有小数
二、寻找左侧边界的二分搜索
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
理解一下这个「左侧边界」有什么特殊含义：
函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，最后退出while的条件是left==right，而left的位置一定是大于等于target的，左边一定小于target。
为什么 left = mid + 1，right = mid ？
当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)
为什么该算法能够搜索左侧边界？
找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
现在希望把while的条件改成<= ？ while 的终止条件应该是 left == right + 1
与上面代码比较，为什么right = mid - 1; 因为 mid 已经搜索过，应该从搜索区间中去除。而上面是左闭右开，mid - 1 并没有搜索过。
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
三、寻找右侧边界的二分查找
也会提供两种写法
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？
终止条件是 left == right，对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了
现在希望把while的条件改成<= ？
当 target 比所有元素都小时，right 会被减到 -1
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况，见下图
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
二分搜索的细节问题需要我们用实例来理解。不用要求太过细枝末节，明白为什么是这样写就行。
算法分析完，也就等于做完下面两题。
704. 二分查找（简单）
34. 在排序数组中查找元素的第一个和最后一个位置（中等）
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
// 寻找左侧边界的二分搜索
let left = 0, right=nums.length-1
while (left<=right) { // 结束时left=right+1
let mid = Math.floor((right-left)/2) + left
const data = nums[mid]
if(data == target){
right = mid - 1
}else if(data > target){
right = mid - 1
}else {
left = mid + 1
}
}
if (left==nums.length || nums[left]!=target) return [-1,-1];
const first = left;
// 寻找右侧边界的二分查找
left = 0, right=nums.length-1
while (left<=right) { // 结束时left=right+1
let mid = Math.floor((right-left)/2) + left
const data = nums[mid]
if(data == target){
left = mid + 1
}else if(data > target){
right = mid - 1
}else {
left = mid + 1
}
}
return [first,right]
};
