java - 如何使用二进制搜索在排序数组中查找重复项？

Question

我试图通过重置 high 变量来扩展一个函数以通过二进制搜索找到整数匹配的数量，但它陷入了循环。我猜一个解决方法是复制此函数以获得最后一个索引以确定匹配数，但我认为这不是一个优雅的解决方案。

来自这里:

public static Matches findMatches(int[] values, int query) {
    int firstMatchIndex = -1;
    int lastMatchIndex = -1;
    int numberOfMatches = 0;

    int low = 0;
    int mid = 0;
    int high = values[values.length - 1];
    boolean searchFirst = false;

    while (low <= high){
        mid = (low + high)/2;

        if (values[mid] == query && firstMatchIndex == -1){
            firstMatchIndex = mid;

            if (searchFirst){
                high = mid - 1;
                searchFirst = false;
            } else { 
                low = mid + 1;
            }

        } else if (query < values[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }           
    }

    if (firstMatchIndex != -1) { // First match index is set
        return new Matches(firstMatchIndex, numberOfMatches);
    }
    else { // First match index is not set
        return new Matches(-1, 0); 
    }
}

像这样:

public static Matches findMatches(int[] values, int query) {
    int firstMatchIndex = -1;
    int lastMatchIndex = -1;
    int numberOfMatches = 0;

    int low = 0;
    int mid = 0;
    int high = values[values.length - 1];
    boolean searchFirst = false;

    while (low <= high){
        mid = (low + high)/2;

        if (values[mid] == query && firstMatchIndex == -1){
            firstMatchIndex = mid;

            if (searchFirst){
                high = values[values.length - 1]; // This is stuck in a loop
                searchFirst = false;
            } 
        } else if (values[mid] == query && lastMatchIndex == -1){
            lastMatchIndex = mid;

            if (!searchFirst){
                high = mid - 1;
            } else { 
                low = mid + 1;
            }
        } else if (query < values[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }

    }

    if (firstMatchIndex != -1) { // First match index is set
        return new Matches(firstMatchIndex, numberOfMatches);
    }
    else { // First match index is not set
        return new Matches(-1, 0); 
    }
}

Answer 1

你的代码有问题:

high = values[values.length - 1];

应该是

high = values.length - 1;

此外，您不需要像 numberOfMatches 和 searchFirst 这样的变量，我们可以有相当简单的解决方案。

现在开始讨论这个问题，我明白你想要什么，我认为二进制搜索适合这种查询。

完成所需的最佳方法是一旦找到匹配项，您只需从该索引向前和向后移动，直到发生不匹配，这在计算 firstMatchIndex 和 numberOfMatches 时既优雅又高效。

所以你的函数应该是:

public static Matches findMatches(int[] values, int query) 
{
 int firstMatchIndex = -1,lastMatchIndex=-1;
 int low = 0,mid = 0,high = values.length - 1;
 while (low <= high)
 {
      mid = (low + high)/2;

      if(values[mid]==query)
      {
          lastMatchIndex=mid;
          firstMatchIndex=mid;
          while(lastMatchIndex+1<values.length&&values[lastMatchIndex+1]==query)
           lastMatchIndex++;
          while(firstMatchIndex-1>=0&&values[firstMatchIndex-1]==query)
           firstMatchIndex--; 
          return new Matches(firstMatchIndex,lastMatchIndex-firstMatchIndex+1); 
      }
      else if(values[mid]>query)
       high=mid-1;
      else low=mid+1;
 }
 return new Matches(-1,0);
}