二进制搜索第一次出现的 k

Question

我有搜索排序数组的代码和 returns 第一次出现 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;
}

我怎么知道什么时候使用左小于或等于右，或者只使用左小于右。

Answer 1

简单说编号

考虑数组只有一个元素的情况，即 {0} 并且要搜索的元素也是 0。

在这种情况下，left == right，但是如果你的条件是while(left<right)，那么searchFirstOfK就会return-1。

此答案在已发布代码的上下文中。如果我们正在谈论替代方案以便我们可以使用 while(left<right) 那么 Matt Timmermans 的答案是正确的并且是一个更好的方法。

下面是 Matt（OP - 我们称之为普通二进制）和 Matt Timmermans（我们称之为优化二进制）的 comparison 针对包含 0 到 5000000 之间的值的列表的方法：

Answer 2

这是一个非常有趣的问题。问题是有一种方法可以让你的二进制搜索总是正确的。问题是确定正确的范围并避免单个元素突出的行为。

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

唯一要记住的关键是你总是把左边作为最小的条件不满足元素，右边作为最大的条件满足元素。这样你就不会被卡住.一旦你理解了这种方法的范围划分，你的二分查找就不会失败。

上面的初始化会给你最大的满足条件的元素。

通过改变初始化可以得到多种元素（比如满足条件的小元素）。

Answer 3

基于对另一个二进制搜索问题的回答：How can I simplify this working Binary Search code in 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且后面所有元素都大于或等于的唯一位置，然后然后它检查看你的值是否正在找的其实是有的

链接的答案强调了以这种方式编写二进制搜索的几个优点。

二进制搜索第一次出现的 k

Binary search for first occurrence of k

algorithm

binary-search