寻找k的第一次出现的二分查找

Question

我有一段代码，用于搜索已排序数组并返回k的第一个出现位置的索引。我想知道是否可以使用

while(left<right) 

替代

while(left<=right)

这是完整的代码：

public static int searchFirstOfK(List<Integer> A, int k) {
   int left = 0, right = A.size() - 1, result = -1;
   // A.subList(left, right + 1) is the candidate set.
   while (left <= right) {
      int mid = left + ((right - left) / 2);
      if (A.get(mid) > k) {
         right = mid - 1;
      } else if (A.get(mid) == k) {
         result = mid;
         // Nothing to the right of mid can be the first occurrence of k.
         right = mid - 1;
      } else { // A.get(mid) < k
         left = mid + 1;
      }
   }
   return result;
}

在什么情况下应该使用“左侧小于或等于右侧”，或只使用“左侧小于右侧”？

- Matt

Answer 1

简单来说，不行。考虑只有一个元素的数组，即{0}，要查找的元素也是0。在这种情况下，left == right，但如果你的条件是while(left<right)，那么searchFirstOfK将返回-1。

---

这个答案是针对发布的代码背景而言的。如果我们在讨论替代方案以便可以使用while(left<right)，那么Matt Timmermans的答案是正确的，而且是更好的方法。

以下是一个比较Matt（原始二分法）和Matt Timmermans（优化二分法）在包含0到5000000之间数值的列表中的方法：

- ZerosAndOnes

Answer 2

在另一个二分搜索问题的答案基础上构建： 如何简化这个工作中的C语言二分搜索代码？

如果您想查找第一次出现的位置，当您找到匹配元素时不能停止。您的搜索应该像这样（当然，这假设列表是已排序的）：

int findFirst(List<Integer> list, int valueToFind)
{
    int pos=0;
    int limit=list.size();
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (list.get(testpos)<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    if (pos < list.size() && list.get(pos)==valueToFind)
        return pos;
    else
        return -1;
}

请注意，每次迭代只需要进行一次比较。二分查找找到唯一的位置，所有前面的元素都小于valueToFind，所有后面的元素都大于或等于它，然后再检查你要查找的值是否实际存在。

链接的答案强调了以这种方式编写二分查找的几个优点。

- Matt Timmermans

Answer 3

这是一个非常有趣的问题。事实上，有一种方法可以使您的二分查找始终正确。关键是确定正确的范围并避免单个元素卡住的行为。

while(left+1<right)
{
   m = (left+right)/2;
   if(check condition is true)
      left = m;
   else
      right =  m;
}

唯一需要记住的关键是，您始终将左侧作为最小条件不满足元素，右侧作为最大条件满足元素。这样你就不会被卡住了。一旦您通过此方法理解了范围划分，您将永远不会在二分搜索中失败。

上述初始化将为您提供最大条件满足元素。

通过更改初始化，您可以获得各种元素（例如小条件满足元素）。

- user2736738

---

这是因为初始化技巧的存在而变得不再必要。@MattTimmermans 我稍作编辑了一下..现在请查看。 - user2736738

OIC。这很不错，但当所有元素都比您要查找的元素大或小时，它可能会出现错误。您需要进行额外的检查。 - Matt Timmermans

啊，马特，是的，在那种情况下需要那个单独的 if 语句。@MattTimmermans - user2736738