algorithm - 二进制搜索第一次出现的 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;
}

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

Answer 1

基于对另一个二进制搜索问题的回答: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 而后面所有元素都大于或等于的唯一位置，然后它会检查你的值是否'要找的其实就在那里。

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