c++ 我们可以用条件前面!=在二进制搜索中结束?

pbpqsu0x  于 2023-08-09  发布在  其他
关注(0)|答案(2)|浏览(105)

我知道我们在二进制搜索中使用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]的条件,所以我认为这段代码应该不会失败。我在一堆测试用例上尝试了它,我得到了正确的答案,但我问的情况是,我错过了任何可能失败的角落情况。

nfeuvbwi

nfeuvbwi1#

您的解决方案中存在许多可能导致不正确结果的小问题。
我会重写它,然后我会描述为什么我做了每一个改变。

std::size_t bin_search(std::vector<int> const& nums, int target) {

字符串
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元素”。一个空向量在这里死亡,你的算法应该是正确的,而不需要在这里进行硬编码检查。

while(front!=end) {


我们保持原样。请注意,!=将正常工作。

auto mid = front + (end-front)/2;


这是一个微妙的差别。我们不是将end和front的索引相加并除以2,这可能会导致色域外的问题,而是将它们之间的距离减半(受64位限制),将其减半,然后将其添加回前面。
因为我们实际上使用的是迭代器,所以这也是法律的的--(随机访问)迭代器上的迭代器减法产生距离积分,可以减半,并将其加回迭代器再次产生迭代器。

if (*mid == target) { return mid-nums.begin(); }
    if (target > *mid) { front = std::next(mid); continue; }
    if (target < *mid) { end = mid; continue; }


这里我改变了退出条件。我只看中路!
我们做了三个方面的比较。这很有用,因为我可以在更现代的C++版本中调用<=>,并在一步中获得值。

}
  return static_cast<std::size_t>(-1);
}


这导致了这个代码:

std::size_t bin_search(std::vector<int> const& nums, int target) {
  auto front = nums.begin();
  auto end = nums.end();
  while(front!=end) {
    auto mid = front + (end-front)/2;

    if (*mid == target) { return mid-nums.begin(); }
    if (target > *mid) { front = std::next(mid); continue; }
    if (target < *mid) { end = mid; continue; }
  }
  return static_cast<std::size_t>(-1);
}


或者,对于更现代的C++:

std::size_t bin_search(std::vector<int> const& nums, int target) {
  auto front = nums.begin();
  auto end = nums.end();
  while(front!=end) {
    auto mid = front + (end-front)/2;

    auto cmp = target <=> *mid;
    if (cmp == 0) { return mid-nums.begin(); }
    if (cmp > 0) { front = std::next(mid); continue; }
    if (cmp < 0) { end = mid; continue; }
  }
  return static_cast<std::size_t>(-1);
}


最后,注意我返回了mid-begin(),它是范围中元素的索引。
...
将其移回基于索引的代码,很可能您遇到了范围恰好包含1个元素的问题,因为您的代码似乎没有使用半开区间。您的代码看起来像是使用了闭合区间,其中nums[end]仍然是范围的一部分。
半开放间隔包含其左侧栅栏立柱,但不包含其右侧栅栏立柱。如果你使用它,一堆算法会工作得更好。

pxy2qtax

pxy2qtax2#

不,这不是一个有效的实现。为什么?为什么?

假设vector<int> nums = {1, 2, 5, 8}int target = 3。让我们看看如何使用!=而不是<=进行二分搜索。(或者说不愿意)

第一次迭代后:

front = 1 end = 3 mid = 1

第二次迭代后:

front = 2 end = 3 mid = 2

在第三次迭代(以及所有其他无限次迭代)之后:

front = 2 end = 1 mid = 2
在这里,<=将完成循环,但由于我们使用的是!=,因此您将陷入永久循环。

所以现在,为什么它不工作?

假设在二分搜索中的左和右在某个点上必须相等是错误的。如果它是真的,那么对于每个NM(其中N表示front和M表示end),例如N < M(N+M)/2+1 <= M(N+M)/2-1 >= N。转换后,我们得到N + 2 <= M,当NM相差一个索引时,这是不正确的。如果在使用!=而不是<=进行二分搜索时发生这种情况,您将得到一个无限循环。
好吧,但我们可以绕过这一点?
和所有事情一样,如果添加了特定的边缘情况,但是除非这样做的唯一原因是为了提高对二分搜索的理解,否则不要这样做。

相关问题