# Kotlin Count number of occurrences (or frequency) in a sorted array

Count number of occurrences (or frequency) in a sorted array
Expected time complexity is O(Logn)

– Example:

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

Solution -> Improved 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);

``````
import java.util.*

fun main() {
var A = intArrayOf(1, 2, 2, 3, 4)
println(solution(A, 2))
}

fun solution(A: IntArray, x: Int): Int {

if (A.size == 0)
return -1

var leftOccur = binarySearchLeftMostOccurs(A, x, 0, A.size - 1)
var rightOccur = leftOccur

if (leftOccur == -1)
return -1
else {
rightOccur = binarySearchRightMostOccurs(A, x, leftOccur, A.size - 1)
}

return rightOccur - leftOccur + 1
}

fun binarySearchLeftMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {

if(leftmost == rightmost) {
if (A[leftmost] == x) {
return leftmost
}

return -1
}

var pivot = (leftmost + rightmost) / 2

if(A[pivot] == x && ((pivot == leftmost) || (A[pivot - 1] < A[pivot]))) {
return pivot
}

if(A[pivot] >= x){
return binarySearchLeftMostOccurs(A, x, leftmost, pivot)
}else {
return binarySearchLeftMostOccurs(A, x, pivot + 1, rightmost)
}
}

fun binarySearchRightMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {
if(leftmost == rightmost) {
if (A[rightmost] == x) {
return rightmost
}

return -1
}

var pivot = (leftmost + rightmost) / 2

if(A[pivot] == x && ((pivot == rightmost) || (A[pivot] < A[pivot + 1]))) {
return pivot
}

if(A[pivot] <= x){
return binarySearchRightMostOccurs(A, x, pivot + 1, rightmost)
}else {
return binarySearchRightMostOccurs(A, x, leftmost, pivot)
}
}
``````
Posted on Categories Kotlin