정렬 된 배열에 숫자가 나타나는 횟수를 검색하는 가장 효율적인 방법

Question

정렬 된 배열에 특정 숫자가 나타나는 횟수를 찾는 효율적인 방법을 찾고 있습니다.

내 현재 코드는 : 그것은 요소의 몇 10 초를인지

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

대답은 정말 선형 스캔을 할 아마 더 효율적, 배열이 시간에 따라 달라집니다. 그것은 더 큰 배열의 경우 다음과 같이 내가 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); 
    } 
}