With the last algorithm, how does it ever return anything but 0? If main calls with start := 0 and end := length - 1? The only case where you get past the base case is if the array is length 1... since (start < end) = (0 < length -1) from the input... and returns 0...

Also, I think there is a good shot at a stack overflow with this method. I would add an extra variable and solve the problem tail recursively.

Try this. int findLeftEdge( int A[], int num, int val ){ int mid = num/2; if( num == 1 ){ return 0; }else{ if( A[mid] == val && A[mid-1] != val ){ return mid; }else if( A[mid] == val || A[mid] > val ){ return findLeftEdge( A, mid, val ); }else if( A[mid] val ){ return findRightEdge( A, mid, val ); } } } int countOccurrenceSortedArray( int A[], int num, int val ){ int left = findLeftEdge( A, num, val ); int right = findRightEdge( A, num, val ); return right-left+1; } int main() { // your code goes here int A[] = { 1, 5, 10, 10, 12, 19, 19, 19, 20, 20}; int ans = countOccurrenceSortedArray( A, sizeof(A)/sizeof(int), 20 ); cout << ans << endl; return 0; }

O(logN) required

JAVA Code : // For Sorted and UnSorted Array in O(N) time Complexity. import java.util.HashMap; public class FindOccurrences { /** * @param args */ public static void main(String[] args) { int unsortedArray[] = {4,6,7,8,4,5,6,8,3,2,4,5,7,8,9,3,4,6,7,8}; System.out.println(findOccurrencesUnsorted(unsortedArray,8)); int sortedArray[] = {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5}; System.out.println(findOccurrencesSorted(sortedArray,5)); } private static int findOccurrencesUnsorted(int[] array, int number) { HashMap map = new HashMap(); for(int i=0;i

O(logN) is possible for sorted arrays, the key here is to firstly check beginning and end to determine next binary-search steps, I attached my code below, and I think this is O(logN) in worst case. //inputs are the sorted array, k is the number looking for //start and end are two index values, main method calls with (start=0) and (end=length-1) int GetOccurance(int[] inputs, int k, int start, int end) { if(startk) return 0; if(inputs[start]==k&&inputs[end]==k) return end-start+1; int mid = (start+end)/2; if(input[mid]k) return GetOccurance(inputs, k, start, mid-1); else return GetOccurance(inputs, k, start, mid-1)+1+GetOccurance(inputs, k, mid+1, end); }

I think it is not possible in O(logN) because anyway traversing the complete array is needed to access all the numbers. Worst Case scenario would be the last number repeating itself 5 times. For example : {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5} and if you are asked to find out the occurrences of number '5' then you have to traverse the complete array once which means the complexity should be O(N).