二进制搜索k的首次出现 [英] Binary search for first occurrence of k

问题描述

我有搜索排序数组并返回首次出现k的索引的代码。
我想知道是否有可能使用

I have code that searches a sorted array and returns the index of the first occurrence of k. I am wondering whether its possible to write this code using

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;
}

我怎么知道何时使用left小于或等于right，或只使用left小于right。

How do I know when to use left is less than or equal to right, or just use left is less than right.

推荐答案

基于此答案的另一个二进制搜索问题：

Building on this answer to another binary search question: How can I simplify this working Binary Search code in C?

如果要查找第一个匹配项的位置，则在找到匹配元素时不能停止。您的搜索应如下所示（当然，这是假定列表已排序）：

If you want to find the position of the first occurrence, you can't stop when you find a matching element. Your search should look like this (of course this assumes that the list is sorted):

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 并且所有后面的元素都大于或等于，然后 then 进行检查

Note that we only need to do one comparison per iteration. The binary search finds the unique position where all the preceding elements are less than valueToFind and all the following elements are greater or equal, and then it checks to see if the value you're looking for is actually there.

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

The linked answer highlights several advantages of writing a binary search this way.

这篇关于二进制搜索k的首次出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！