Count the number of occurrences in a sorted array

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)

Examples:

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
  Output: 4 // x (or 2) occurs 4 times in arr[]

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 3
  Output: 1 

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 1
  Output: 2 

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 4
  Output: -1 // 4 doesn't occur in arr[] 

Method 1 (Linear Search)
Linearly search for x, count the occurrences of x and return the count.

Time Complexity: O(n)

Method 2 (Use Binary Search)
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

public int countNumbers(int[] a, int t) {
    if(a==null || a.length==0) return 0;
    int left = getLeftIndex(a, t);
    int right = getRightIndex(a, t);
    if(left == -1 || right == -1) return 0;
    return right-left+1;
}

private int getLeftIndex(int[] a, int t) {
    int start = 0, end = a.length;
    while(start <= end) {
        int mid = (start + end) / 2;
        if((mid == 0 || a[mid-1] < t) && a[mid] == t) {
            return mid;
        } else if(a[mid] < t) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
} 

private int getRightIndex(int[] a, int t) {
    int start = 0, end = a.length;
    while(start <= end) {
        int mid = (start + end) / 2;
        if((mid == a.length-1 || a[mid+1] > t) && a[mid] == t) {
            return mid;
        } else if(a[mid] > t) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return -1;
} 

 

Method 3:

下面这种递归的方法更好理解。

private int count(int[] A, int s, int e, int x) {
	if(s > e) return 0;
	int mid = (s + e)/2;
 
	if(A[mid] == x) {
		return 1 + count(A, s, mid - 1, x) + count(A, mid + 1, e, x);
	} else if(A[mid] > x) {
		return count(A, s, mid - 1, x);
 	} else {
 		return count(A, mid + 1, e, x);
 	}
}

public int countNumber(int[] A, int x) {
	return count(A, 0, A.length-1, x);
}

 

Reference:

http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/