• 0

Count number of occurence in a sorted array
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3620)

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


Posted Answers

  • Posted: 7 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;
 }
You need to Sign In to post your solution.