最有效的方法來搜索多少多少次出現在一個有序數組

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