Count number of occurrences of a number

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)
  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
  Output: 4


  1. we can apply a variant of binary search
    we can find d first and last occurence of the element in the array
    no. of occurencec= last-first+1

  2. @Navin yes you can solve in the way you mentioned ...this will be o(logn) solution..


Post a Comment

Popular posts from this blog