基础模板
function binarySearch(nums, target) {
let left = 0, right = ...;
while(...) {
let mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
注意:
- 不要出现 else
计算 mid 时需要防止溢出,代码中
left + (right - left) / 2
就和(left + right) / 2
的结果相同,但是有效防止了left
和right
太大直接相加导致溢出一、寻找一个数(基本的二分搜索
此算法是左闭右闭
- 【 left,right 】
function binarySearch( nums, target) {
let left = 0;
let right = nums.length - 1; // 注意
while(left <= right) {
let mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
二、寻找左侧边界的二分搜索
- 此算法是左闭右开
- 【 left,right )
function left_bound(nums, target) {
if (nums.length == 0) return -1;
let left = 0;
let right = nums.length; // 注意
while (left < right) { // 注意
let mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
if (left == nums.length || nums[left] !== target ) {
return -1;
}
return left;
}
边界问题的讨论
如果target 是0 ,不在区间范围内,如图所示
那么在寻找的过程中,right就会一直往左缩减,最后成为如下所示的样子
此时,不符合left<right,遍历结束,触发边界
nums[left] !== target
如果是一个极大值呢?
在第一轮循环之后演变成如下图所示
此时再次循环的话left 会落在如下位置
超出范围触发边界
left == nums.length
极大极小的情况有了,那如果是在区间内,没有找到值呢
最终都会触发
nums[left] !== target
统一一下都变成左闭右闭
function left_bound(nums, target) {
let left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
let 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;
}
三、寻找右侧边界的二分搜索
- 此算法是左闭右开
- 【 left,right )
function right_bound( nums, target) {
if (nums.length == 0) return -1;
let left = 0, right = nums.length;
while (left < right) {
let mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left == 0 || nums[right] != target) {
return -1
};
return left - 1; // 注意
}
四、三者统一的二分算法模板
将「搜索区间」全都统一成两端都闭,好记,只要稍改 nums[mid] == target
条件处的代码和返回的逻辑即可
// 搜索一个数
function binary_search(nums, target) {
let left = 0, right = nums.length - 1;
while(left <= right) {
let 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) {
// 搜索一个数直接返回
// 搜索左侧边界,右值减小
// 搜索右侧边界,左值减小
...
...
...
}
}
// 处理左右侧边界越界问题
...
...
...
// 返回
return ...;
}
// 搜索一个数
function binary_search(nums, target) {
let left = 0, right = nums.length - 1;
while(left <= right) {
let 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) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
// 寻找左侧边界的二分搜索
function left_bound(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let 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) {
// 别返回,锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
// 寻找右侧边界的二分搜索
function right_bound(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
let 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;
}
总结
建议使用统一二分模板,不去考虑左闭右开或者左右闭合的边界问题
- 选用左右都闭合,left = 0,right = arr.length-1
- 在left < right 的循环范围内去寻找目标值
- 找目标
- 如果是寻找目标,当 nums[mid] = target 时候就返回
- 如果是寻找左边界,当 nums[mid] = target 时候就向左查找
- 当不满足循环的时候处理边界,返回left
- 边界是left >= nums.length || nums[left]!==target
- 如果是寻找右边界,当 nums[mid] = target 时候就向右查找
- 当不满足循环的时候处理边界,返回right
- 边界是right <0 || nums[right]!==target