1. 存在的问题:
a. 二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量;
b. 到底是 while(left < right) 还是 while(left <= right);
c. 到底是 right = middle呢,还是要right = middle - 1;
2. 二分法的第一种写法:[left, right] 左闭右闭区间
a. 注意:
i. while (left <= right),因为left == right 在区间 [left, right] 是有意义的=;
ii. if (nums[middle] > target), right = middle - 1,因为当前这个 nums[middle] 一定不是 target,那么接下来要查找的区间为 [left,middle - 1];
b. 代码实现:
const search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
// 当 left==right,区间 [left, right] 依然有效
while (left <= right) {
let mid = left + Math.floor((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] === target) {
return mid;
}
}
return -1;
}
c. 代码优化:(此方法仅用于 nums 中一定能找到 target 或返回 mid 位置,不能用于找不到的情况)
i. 根据 if 的判断条件, left 左边的值一直保持 小于 target, right 右边的值一直保持大于等于 target;
ii. 无论数组个数是奇数个还是偶数个,left 最终一定等于 mid, 所以最终答案一定在 left 的位置;
let searchInsert = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = left + Math.floor((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
3. 二分法的第二种写法:[left, right) 左闭右开区间
a. 注意:
i. while (left < right),因为 left == right 在区间 [left, right) 是没有意义的;
ii. if (nums[middle] > target) ,right = middle,因为当前 nums[middle] 不等于 target,去左区间继续寻找,而寻找区间是左闭右开区间,所以 right = middle,即:下一个查询区间不会去比较 nums[middle];
b. 代码实现:
const search = function (nums, target) {
let left = 0;
let right = nums.length;
// 定义 target 在左闭右开的区间里,即:[left, right)
// 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
while (left < right) {
let mid = left + Math.floor((right - left) >> 1);
if (nums[mid] > target) {
// target 在左区间,在 [left, mid) 中
right = mid;
} else if (nums[mid] < target) {
// target 在右区间,在 [middle + 1, right) 中
left = mid + 1;
} else if (nums[mid] === target) {
return mid;
}
}
return -1;
}
0 Comments