我知道我们在二进制搜索中使用while(front <= end)
。我在想,我们可以像这里的代码一样使用条件while(front != end)
吗?我找不到一个可能失败的案例。
class BinarySearch {
public:
int bin_search(vector<int>& nums, int target) {
int count = nums.size();
int front = 0;
int end = count - 1;
if(nums[0]==target){return 0;}
while(front!=end){
int mid = (end + front)/2;
// cout<<mid<<endl;
if(nums[front] == target){return front;}
else if(nums[end] == target){return end;}
else if(nums[mid]==target){return mid;}
else if(nums[mid]<target){
front = mid+1;
}
else if(nums[mid]>target){
end = mid - 1;
}
}
return -1;
}
};
字符串
因为我在每个while循环中检查nums[front]和nums[end]的条件,所以我认为这段代码应该不会失败。我在一堆测试用例上尝试了它,我得到了正确的答案,但我问的情况是,我错过了任何可能失败的角落情况。
2条答案
按热度按时间nfeuvbwi1#
您的解决方案中存在许多可能导致不正确结果的小问题。
我会重写它,然后我会描述为什么我做了每一个改变。
字符串
1.用
const&
把你的集装箱拿走。1.返回一个
std::size_t
而不是一个int
;int
通常是32位,即使在64位机器上,大小为2^31-1的向量也可以由现代计算机处理。通过返回一个int
,可以限制算法可以处理的内容。在64位机器上,size_t
是64位的,这将足以在至少未来几十年甚至几个世纪内处理任何std::vector
。int n = nums.开始(); int count = count. count();通过使用迭代器而不是索引,并通过使用半开区间,产生了一系列的好处。
半开音程非常自然地处理空音程--开始和结束是相等的。
迭代器而不是索引都快一点,并防止你混淆你的值空间和你的迭代空间。
我们还删除了“check the 0元素”。一个空向量在这里死亡,你的算法应该是正确的,而不需要在这里进行硬编码检查。
型
我们保持原样。请注意,
!=
将正常工作。型
这是一个微妙的差别。我们不是将end和front的索引相加并除以2,这可能会导致色域外的问题,而是将它们之间的距离减半(受64位限制),将其减半,然后将其添加回前面。
因为我们实际上使用的是迭代器,所以这也是法律的的--(随机访问)迭代器上的迭代器减法产生距离积分,可以减半,并将其加回迭代器再次产生迭代器。
型
这里我改变了退出条件。我只看中路!
我们做了三个方面的比较。这很有用,因为我可以在更现代的C++版本中调用
<=>
,并在一步中获得值。型
这导致了这个代码:
型
或者,对于更现代的C++:
型
最后,注意我返回了
mid-begin()
,它是范围中元素的索引。...
将其移回基于索引的代码,很可能您遇到了范围恰好包含1个元素的问题,因为您的代码似乎没有使用半开区间。您的代码看起来像是使用了闭合区间,其中
nums[end]
仍然是范围的一部分。半开放间隔包含其左侧栅栏立柱,但不包含其右侧栅栏立柱。如果你使用它,一堆算法会工作得更好。
pxy2qtax2#
不,这不是一个有效的实现。为什么?为什么?
假设
vector<int> nums = {1, 2, 5, 8}
和int target = 3
。让我们看看如何使用!=
而不是<=
进行二分搜索。(或者说不愿意)第一次迭代后:
front
= 1end
= 3mid
= 1第二次迭代后:
front
= 2end
= 3mid
= 2在第三次迭代(以及所有其他无限次迭代)之后:
front
= 2end
= 1mid
= 2在这里,
<=
将完成循环,但由于我们使用的是!=
,因此您将陷入永久循环。所以现在,为什么它不工作?
假设在二分搜索中的左和右在某个点上必须相等是错误的。如果它是真的,那么对于每个
N
和M
(其中N表示front
和M表示end
),例如N < M
:(N+M)/2+1 <= M
和(N+M)/2-1 >= N
。转换后,我们得到N + 2 <= M
,当N
和M
相差一个索引时,这是不正确的。如果在使用!=
而不是<=
进行二分搜索时发生这种情况,您将得到一个无限循环。好吧,但我们可以绕过这一点?
和所有事情一样,如果添加了特定的边缘情况,但是除非这样做的唯一原因是为了提高对二分搜索的理解,否则不要这样做。