我写了首诗,把二分搜索算法变成了默写题 :: labuladong的算法小抄 #1011
Replies: 115 comments 21 replies
-
自己验证了下34题,不能直接套用,有些case没有过,期望修复 |
Beta Was this translation helpful? Give feedback.
-
@Calmlzw @theSavageseens 说具体一些?我试了下可以通过的。 |
Beta Was this translation helpful? Give feedback.
-
试了34题,python是没问题的(下面答案里有个大哥建议直接用.index()笑死) |
Beta Was this translation helpful? Give feedback.
-
试了34题,Java是没问题的 |
Beta Was this translation helpful? Give feedback.
-
C++也通过了,上面出错的同学,应该是没有注意循环后的细节吧?(比如我就是左边界忘记检查等于数组大小的时候了😥) |
Beta Was this translation helpful? Give feedback.
-
秒 |
Beta Was this translation helpful? Give feedback.
-
妙呀 |
Beta Was this translation helpful? Give feedback.
-
双闭区间是精髓 |
Beta Was this translation helpful? Give feedback.
-
寻找左侧边界的⼆分搜索中 |
Beta Was this translation helpful? Give feedback.
-
能否也讲解一下,如果数组里面不含有查找元素,那么如果找最左和最右,返回的值是否可以保证是数组里第一个比target大或者小的数? |
Beta Was this translation helpful? Give feedback.
-
C,34题没问题(双闭区间) |
Beta Was this translation helpful? Give feedback.
-
不好意思,又重新验证了下,是正确的,之前应该是自己哪里弄错了,麻烦把这个issue删了吧,总是有推送邮件 |
Beta Was this translation helpful? Give feedback.
-
一开始就判断 target 是否存在,最后就不用考虑越界的事了。 if (target < nums[left] || target > nums[right]) {
return -1;
} |
Beta Was this translation helpful? Give feedback.
-
请问大家我这样判断空数组为什么了leetcode不给过啊 |
Beta Was this translation helpful? Give feedback.
-
@JiachengZhao98 |
Beta Was this translation helpful? Give feedback.
-
寻找左侧边界时,通过不断左移right,逼近左侧边界,left始终锚定左侧边界;也就是: if (left == nums.length || nums[left] != target) 寻找右侧边界时,通过不断右移left,逼近右侧边界,right始终锚定右侧边界;也就是: if (right < 0 || nums[right] != target) |
Beta Was this translation helpful? Give feedback.
-
打卡喽,跟着东哥学算法,越学越上瘾,希望东哥能继续更新好作品!!感谢东哥 |
Beta Was this translation helpful? Give feedback.
-
寻找一个数(基本的二分搜索)小结中: 寻找左侧边界的二分搜索小结中: 都是使用while(left < right)判断,达到终止条件后,为什么第1个搜索区间是[right, right],区间非空,而第2个搜索区间是 [left, left) 区间为空。 |
Beta Was this translation helpful? Give feedback.
-
实际写的时候要注意越界的判别 if (left - 1 < 0) return -1; 后面加个else就行 |
Beta Was this translation helpful? Give feedback.
-
我觉得比如right=mid+1的核心原因不是因为mid 已经搜索过,应该从搜索区间中去除,这种说法太模糊了。事实上,如果mid不+1的话,因为整除的向下取整,会导致结果在一个值原地踏步,得不到正确的结果 |
Beta Was this translation helpful? Give feedback.
-
对于第四条的逻辑统一的写法里,统一的left_bound的最后的判断条件有问题,left<.这个判断条件是无意义的,因为不会出现left<0的情况,在这个函数里,left初始化为0,后续没有对left进行左移操作,同理,right_bound中也不需要判断right>=nums.length,因为right没有进行过右移操作 |
Beta Was this translation helpful? Give feedback.
-
还是不懂为什么要left - 1, |
Beta Was this translation helpful? Give feedback.
-
仔细推导了一下。。。下面是闭区间的分析 寻找右边界(<=target的index最大者)的时候,因为nums[mid]<=target时,left = mid +1;当nums[mid]>target的时候right = mid-1; |
Beta Was this translation helpful? Give feedback.
-
怎么感觉有些地方return left-1和right需不需要减一写错了,前面例子的代码和后面例子的代码不同。(可以这样说模板给的太多不易观看) |
Beta Was this translation helpful? Give feedback.
-
记得以前大神的写法是: |
Beta Was this translation helpful? Give feedback.
-
东哥,在 同理,在在 |
Beta Was this translation helpful? Give feedback.
-
总结二分搜索任意位置(binarySearchAny),二分搜索左边界(binarySearchLeft) 和 二分搜索右边界(binarySearchRight) 3 个算法的通用模板。下文 nums[a..b) 表示法表示 nums 的子区间,"[", "]" 表示闭区间,"(", ")" 表示开区间。
int binarySearchAny(int[] nums, int start, int end, int target) {
int targetIndex = -1;
int left = start, right = end;
while (left <= right) {
int mid = left + (right - left) / 2;
int midNum = nums[mid];
if (target < midNum) right = mid - 1;
else if (target > midNum) left = mid + 1;
else {
targetIndex = mid;
break;
}
}
return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
}
int binarySearchLeft(int[] nums, int start, int end, int target) {
int targetIndex = -1;
int left = start, right = end;
while (left <= right) {
int mid = left + (right - left) / 2;
int midNum = nums[mid];
if (target < midNum) right = mid - 1;
else if (target > midNum) left = mid + 1;
else {
targetIndex = mid;
right = mid - 1;
}
}
return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
}
int binarySearchRight(int[] nums, int start, int end, int target) {
int targetIndex = -1;
int left = start, right = end;
while (left <= right) {
int mid = left + (right - left) / 2;
int midNum = nums[mid];
if (target < midNum) right = mid - 1;
else if (target > midNum) left = mid + 1;
else {
targetIndex = mid;
left = mid + 1;
}
}
return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
} |
Beta Was this translation helpful? Give feedback.
-
leetcode 34题,CPP最优雅解法 class Solution {
int lowerBound(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == target)
right = mid-1;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid-1;
}
if (left == nums.size() || nums[left] != target)
return -1;
return left;
}
int upperBound(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
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
right = mid - 1;
}
if (right < 0 || nums[right] != target)
return -1;
return right;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
return {lowerBound(nums, target), upperBound(nums, target)};
}
}; |
Beta Was this translation helpful? Give feedback.
-
我的理解搜索区间的开闭问题
left和right的移动问题首先明确一点 |
Beta Was this translation helpful? Give feedback.
-
是我笑点太低吗?开头的笑话我笑了很久😂 |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里:我写了首诗,把二分搜索算法变成了默写题
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions