最有效的方法来搜索多少多少次出现在一个有序数组

Question

我正在寻找一种有效的方式来找到特定数量的多少次出现在排序后的数组。

我当前的代码：

public class Numbers { 

    public static void main(String[] args) { 
     int[] x = new int[]{1,2,3,4,4,7,7,7,7,7,8}; 
     int count = 0; 
     for (int i = 0; i < x.length; ++i) 
      if (x[i] == 7) ++count; 
     System.out.println(count); 
    } 
} 

Answer 1

答案真的取决于你的阵列有多长，如果这只是元素的几个10S，它可能是更有效地做线性扫描。如果它是一个更大的阵列，我推荐使用Array.binarySearch()，如下：

public static void main(String[] args) { 
    int[] x = new int[]{1,2,3,4,4,7,7,7,7,7,8}; 
    int index = Arrays.binarySearch(x, 7); 
    System.out.println(index); 
    int count = 0; 
    if (index >= 0) { 
     // search down 
     int i = index - 1; 
     for (; i >= 0 && x[i] == 7; --i) { 
     } 
     // search up 
     for (++index; index < x.length && x[index] == 7; ++index) { 
     } 
     count = index - (i + 1); 
    } 
    System.out.println(count); 
} 

首先二进制搜索会告诉你，如果这个产品目前在数组中，如果是，你真的不知道在哪里在搜索范围内找到了元素，但是您必须在两个方向上进行线性扫描才能确定确切的计数，但是您必须执行的比较次数最多只是此特定键的计数......（不包括二进制搜索）

Answer 2

由于数组进行排序，如在评论中提到的，你可以执行2个二进制搜索找到数组中的最低索引，其中数字出现，其中出现次数最高的指数。添加二进制搜索以找到某些索引，并获得O（log n）算法。

尝试此代码不与一些不同的阵列值。

public static void main(final String[] args) { 
    final int numberToCount = 7; 

    final int[] x = new int[]{1,2,3,4,4,6,6,6,6,7,7,7,7,7,8,8,8,8,8,8}; 

    final int indexOfKnownOccurence = Arrays.binarySearch(x, numberToCount); 
    if (indexOfKnownOccurence < 0) { 
     System.out.println("No instances of the number found"); 
     return; 
    } 

    final int lowerBound = findIndexOfFirstOccurence(x, numberToCount, 0, indexOfKnownOccurence); 

    final int upperBound = findIndexOfLastOccurence(x, numberToCount, indexOfKnownOccurence, x.length - 1); 

    System.out.println("Lower bound: " + lowerBound); 
    System.out.println("Upper bound: " + upperBound); 
    System.out.println("Number of occurrences: " + (upperBound - lowerBound + 1)); 
} 

//Binary search for start index 
public static int findIndexOfFirstOccurence(final int[] x, final int numberToFind, final int startIndex, final int endIndex) { 
    if (startIndex == endIndex) { 
     return startIndex; 
    } else if (x[startIndex] == numberToFind) { 
     return startIndex; 
    } else if (startIndex + 1 == endIndex) { 
     return endIndex; 
    } 

    final int midIndex = startIndex + (int)Math.floor((endIndex - startIndex)/2); 

    if (x[midIndex] == numberToFind) { 
     return findIndexOfFirstOccurence(x, numberToFind, startIndex, midIndex); 
    } else { 
     return findIndexOfFirstOccurence(x, numberToFind, midIndex, endIndex); 
    } 
} 

//Binary search for end index 
public static int findIndexOfLastOccurence(final int[] x, final int numberToFind, final int startIndex, final int endIndex) { 
    if (startIndex == endIndex) { 
     return endIndex; 
    } else if (x[endIndex] == numberToFind) { 
     return endIndex; 
    } else if (startIndex + 1 == endIndex) { 
     return startIndex; 
    } 

    final int midIndex = startIndex + (int)Math.floor((endIndex - startIndex)/2); 

    if (x[midIndex] == numberToFind) { 
     return findIndexOfLastOccurence(x, numberToFind, midIndex, endIndex); 
    } else { 
     return findIndexOfLastOccurence(x, numberToFind, startIndex, midIndex); 
    } 
}