我们可以在二分查找中使用条件 front != end 吗？

Question

我知道我们在二分查找中使用

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] 的条件，因此我认为这段代码不会失败。我在一堆测试用例上尝试过，得到了正确的答案，但我想问一下，以防万一我错过了任何可能失败的极端情况。

Answer 1

您的解决方案存在许多小问题，可能会导致错误的结果。

我会重写它，然后我会描述我进行每项更改的原因。

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

1. 通过

   const&

   拿走您的容器。

2. 返回

   std::size_t

   而不是

   int

   ；即使在 64 位机器上，

   int

   通常也是 32 位，现代计算机可以处理大小为 2^31-1 的向量。通过返回

   int

   ，您可以限制算法可以处理的内容。在 64 位机器上，

   size_t

   是 64 位，这足以处理至少未来几十年（如果不是几个世纪）的任何

   std::vector

   。

   auto front = nums.begin(); 自动结束 = nums.end(); 通过使用迭代器而不是索引并使用半开区间，可以产生很多好处。

半开区间非常自然地处理空区间 - 起点和终点相等。

迭代器而不是索引都更快一点，并且可以防止您将值空间与迭代空间混淆。

我们还删掉了“检查0元素”。一个空向量在这里消失，你的算法应该是正确的，无需在这里进行硬编码检查。

  while(front!=end){

我们保持不变。请注意，

!=

可以正常工作。

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

这是一个微妙的区别。我们不是将 end 和 front 的索引相加并除以 2，这可能会导致色域外问题，而是取它们之间距离的一半（受 64 位限制），将其减半，然后将其添加到前面.

因为我们实际上使用的是迭代器，所以这也是合法的 - （随机访问）迭代器上的迭代器减法会产生距离积分，该距离积分可以减半，并将其加回迭代器再次产生迭代器。

    if (*mid == target) { return mid-nums.begin(); }
    if (*mid < target) { front = std::next(mid); continue; }
    if (*mid > target) { 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 (*mid < target) { front = std::next(mid); continue; }
    if (*mid > target) { end = std::prev(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 = *mid <=> target;
    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]

仍然是您范围的一部分。

半开间隔包含其左侧栅栏柱，但不包含其右侧栅栏柱。如果你使用一堆算法，效果会更好。