fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
我写了首诗，把二分搜索算法变成了默写题 :: labuladong的算法小抄
寻找左侧边界的⼆分搜索中 // target 比所有数都大 if (left == nums.length) return -1; 不是应该返回nums.length嘛？
自己验证了下34题，不能直接套用，有些case没有过，期望修复
不好意思，又重新验证了下，是正确的，之前应该是自己哪里弄错了，麻烦把这个issue删了吧，总是有推送邮件
一开始就判断 target 是否存在，最后就不用考虑越界的事了。
if (target < nums[left] || target > nums[right]) {
return -1;
}
请问大家我这样判断空数组为什么了leetcode不给过啊 if(nums.size() == 0) { return {-1, -1}; } leetcode一直显示runtime error
while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right] 这句话的区间写错了吧应该是[right,right)
js 版，需要加一个 Math.floor
function binarySearch(nums, target) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] == target) {
// 直接返回
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 直接返回
return -1;
}
function leftBoundSearch(nums, target) {
if (nums.length == 0) return -1;
let left = 0;
let right = nums.length - 1; // 注意
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
right = mid - 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1; // 注意
} else {
right = mid - 1; // 注意
}
}
// target 比所有数都大
if (left >= nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] === target ? left : -1;
}
function rightBoundSearch(nums, target) {
if (nums.length == 0) return -1;
let left = 0;
let right = nums.length - 1; // 注意
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1; // 注意
} else {
right = mid - 1; // 注意
}
}
// target 比所有元素都小
if (right < 0) return -1;
// 类似之前算法的处理方式
return nums[right] === target ? right : -1;
}
console.log(binarySearch([5, 8, 8, 8, 8, 10], 8));
console.log(leftBoundSearch([5, 8, 8, 8, 8, 10], 8));
console.log(rightBoundSearch([5, 8, 8, 8, 8, 10], 8));
寻找左侧边界的时候检查出界情况为什么要用 if (left >= nums.length） left越界最大不就是nums.length吗，难道left还有大于nums.length的情况？
youthlql commented a day ago 在找左侧边界的代码中，为何只考虑了left越界，没有考虑right也有可能越界。同理为何在右侧边界中只考虑了right越界，而没有考虑left越界 youthlql commented a day ago 比如说在寻找左侧边界中，target比最左边的数还小，那么rigth就会一直减小，直到<0越界，而代码中并没有考虑。 @labuladong 这个能讲下吗？
youthlql commented a day ago 在找左侧边界的代码中，为何只考虑了left越界，没有考虑right也有可能越界。同理为何在右侧边界中只考虑了right越界，而没有考虑left越界 youthlql commented a day ago 比如说在寻找左侧边界中，target比最左边的数还小，那么rigth就会一直减小，直到<0越界，而代码中并没有考虑。 @labuladong 这个能讲下吗？
这个代码考虑了，但是文章里面没细说
在找左侧边界的代码中，为何只考虑了left越界，没有考虑right也有可能越界。同理为何在右侧边界中只考虑了right越界，而没有考虑left越界
假设Right 一直在往Left逼近，最极端情况就是Left一直保持初始值为0不变，Right逼近到最后就等于了Left，然后退出循环，这种情况下Right也不过等于0，不会越界。
