Count number of occurence in a sorted array sortedarray array searching    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (2861)

Suppose you are given a sorted array. How will you count the number of occurrence of a given key?

 Posted: 5 years ago 0 0 Edit Since the array is sorted and we are finding the number of occurrences of a given key, the key will be distributed in the array in a certain range. Therefore, we have to find the beginning and end of that range. The length of the range will determine the number. We can find that modifying the binary search.Time complexity = $$O(logn)$$.public static int findBeginIndex(int[] array,int key,int low,int high) { int middle; while(low < = high) { middle = high - (high - low) / 2; if( (middle == 0 || array[middle - 1] != key) & & array[middle] == key) return middle; elseif(array[middle] < = key) high = mid - 1; else low = mid + 1; } return -1; }public static int findEndIndex(int[] array,int key,int low,int high){ int middle; while(low < = high) { middle = high - (high - low) / 2; if( (middle == array.length-1 || array[middle + 1] != key) & & array[middle] == key) return middle; else if(array[middle] < = key) low = mid + 1; else high = mid - 1; } return -1; }