Count number of occurrences (or frequency) in a sorted array
Last Updated :
20 Dec, 2023
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)
Examples:
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 3
Output: 1
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 1
Output: 2
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 4
Output: -1 // 4 doesn't occur in arr[]
Method 1 (Linear Search)
Linearly search for x, count the occurrences of x and return the count.
C++
#include <stdio.h>
int countOccurrences(int arr[], int n, int x)
{
int res = 0;
for (int i = 0; i < n; i++)
if (x == arr[i])
res++;
return res;
}
int main()
{
int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
printf("%d", countOccurrences(arr, n, x));
return 0;
}
|
C
#include <stdio.h>
int main() {
return 0;
}
|
Java
class Main
{
static int countOccurrences(int arr[], int n, int x)
{
int res = 0;
for (int i=0; i<n; i++)
if (x == arr[i])
res++;
return res;
}
public static void main(String args[])
{
int arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };
int n = arr.length;
int x = 2;
System.out.println(countOccurrences(arr, n, x));
}
}
|
Python3
def countOccurrences(arr, n, x):
res = 0
for i in range(n):
if x == arr[i]:
res += 1
return res
arr = [1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]
n = len(arr)
x = 2
print (countOccurrences(arr, n, x))
|
C#
using System;
class GFG
{
static int countOccurrences(int []arr,
int n, int x)
{
int res = 0;
for (int i = 0; i < n; i++)
if (x == arr[i])
res++;
return res;
}
public static void Main()
{
int []arr = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };
int n = arr.Length;
int x = 2;
Console.Write(countOccurrences(arr, n, x));
}
}
|
Javascript
<script>
function countOccurrences(arr,n,x)
{
let res = 0;
for (let i=0; i<n; i++)
{
if (x == arr[i])
res++;
}
return res;
}
arr=[1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]
let n = arr.length;
let x = 2;
document.write(countOccurrences(arr, n, x));
</script>
|
PHP
<?php
function countOccurrences($arr, $n, $x)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
if ($x == $arr[$i])
$res++;
return $res;
}
$arr = array(1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 );
$n = count($arr);
$x = 2;
echo countOccurrences($arr,$n, $x);
?>
|
Output :
4
Time Complexity: O(n)
Space Complexity: O(1), as no extra space is used
Method 2 (Better using Binary Search)
We first find an occurrence using binary search. Then we match toward left and right sides of the matched the found index.
C++
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
int countOccurrences(int arr[], int n, int x)
{
int ind = binarySearch(arr, 0, n - 1, x);
if (ind == -1)
return 0;
int count = 1;
int left = ind - 1;
while (left >= 0 && arr[left] == x)
count++, left--;
int right = ind + 1;
while (right < n && arr[right] == x)
count++, right++;
return count;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
cout << countOccurrences(arr, n, x);
return 0;
}
|
C
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
int countOccurrences(int arr[], int n, int x)
{
int ind = binarySearch(arr, 0, n - 1, x);
if (ind == -1)
return 0;
int count = 1;
int left = ind - 1;
while (left >= 0 && arr[left] == x)
{
count++;
left--;
}
int right = ind + 1;
while (right < n && arr[right] == x)
{
count++;
right++;
}
return count;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
printf("%d", countOccurrences(arr, n, x));
return 0;
}
|
Java
class GFG
{
static int binarySearch(int arr[], int l,
int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l,
mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
static int countOccurrences(int arr[],
int n, int x)
{
int ind = binarySearch(arr, 0,
n - 1, x);
if (ind == -1)
return 0;
int count = 1;
int left = ind - 1;
while (left >= 0 &&
arr[left] == x)
{
count++;
left--;
}
int right = ind + 1;
while (right < n &&
arr[right] == x)
{
count++;
right++;
}
return count;
}
public static void main(String[] args)
{
int arr[] = {1, 2, 2, 2, 2,
3, 4, 7, 8, 8};
int n = arr.length;
int x = 2;
System.out.print(countOccurrences(arr, n, x));
}
}
|
Python 3
def binarySearch(arr, l, r, x):
if (r < l):
return -1
mid = int( l + (r - l) / 2)
if arr[mid] == x:
return mid
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)
return binarySearch(arr, mid + 1,
r, x)
def countOccurrences(arr, n, x):
ind = binarySearch(arr, 0, n - 1, x)
if ind == -1:
return 0
count = 1
left = ind - 1
while (left >= 0 and
arr[left] == x):
count += 1
left -= 1
right = ind + 1;
while (right < n and
arr[right] == x):
count += 1
right += 1
return count
arr = [ 1, 2, 2, 2, 2,
3, 4, 7, 8, 8 ]
n = len(arr)
x = 2
print(countOccurrences(arr, n, x))
|
C#
using System;
class GFG
{
static int binarySearch(int[] arr, int l,
int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l,
mid - 1, x);
return binarySearch(arr, mid + 1,
r, x);
}
static int countOccurrences(int[] arr,
int n, int x)
{
int ind = binarySearch(arr, 0,
n - 1, x);
if (ind == -1)
return 0;
int count = 1;
int left = ind - 1;
while (left >= 0 &&
arr[left] == x)
{
count++;
left--;
}
int right = ind + 1;
while (right < n &&
arr[right] == x)
{
count++;
right++;
}
return count;
}
public static void Main()
{
int[] arr = {1, 2, 2, 2, 2,
3, 4, 7, 8, 8};
int n = arr.Length;
int x = 2;
Console.Write(countOccurrences(arr, n, x));
}
}
|
Javascript
<script>
function binarySearch(arr, l, r, x)
{
if (r < l)
return -1;
var mid = l + parseInt((r - l) / 2);
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
function countOccurrences(arr, n, x)
{
var ind = binarySearch(arr, 0, n - 1, x);
if (ind == -1)
return 0;
var count = 1;
var left = ind - 1;
while (left >= 0 && arr[left] == x)
count++, left--;
var right = ind + 1;
while (right < n && arr[right] == x)
count++, right++;
return count;
}
var arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
var n = arr.length;
var x = 2;
document.write(countOccurrences(arr, n, x));
</script>
|
PHP
<?php
function binarySearch(&$arr, $l,
$r, $x)
{
if ($r < $l)
return -1;
$mid = $l + ($r - $l) / 2;
if ($arr[$mid] == $x)
return $mid;
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
return binarySearch($arr, $mid + 1,
$r, $x);
}
function countOccurrences($arr, $n, $x)
{
$ind = binarySearch($arr, 0,
$n - 1, $x);
if ($ind == -1)
return 0;
$count = 1;
$left = $ind - 1;
while ($left >= 0 &&
$arr[$left] == $x)
{
$count++;
$left--;
}
$right = $ind + 1;
while ($right < $n &&
$arr[$right] == $x)
{
$count++;
$right++;
}
return $count;
}
$arr = array( 1, 2, 2, 2, 2,
3, 4, 7, 8, 8 );
$n = sizeof($arr);
$x = 2;
echo countOccurrences($arr, $n, $x);
?>
|
Output :
4
Time Complexity : O(Log n + count) where count is number of occurrences.
Space Complexity: O(logn), due to recursive stack space
Method 3 (Best using 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);
C++
# include <bits/stdc++.h>
using namespace std;
int count(int arr[], int x, int n)
{
int *low = lower_bound(arr, arr+n, x);
if (low == (arr + n) || *low != x)
return 0;
int *high = upper_bound(low, arr+n, x);
return high - low;
}
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3;
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
return 0;
}
|
C
# include <stdio.h>
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2;
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
int last(int arr[], int low, int high, int x, int n)
{
if (high >= low)
{
int mid = (low + high)/2;
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
int count(int arr[], int x, int n)
{
int i;
int j;
i = first(arr, 0, n-1, x, n);
if(i == -1)
return i;
j = last(arr, i, n-1, x, n);
return j-i+1;
}
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3;
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}
|
Java
class Main
{
static int count(int arr[], int x, int n)
{
int i;
int j;
i = first(arr, 0, n-1, x, n);
if(i == -1)
return i;
j = last(arr, i, n-1, x, n);
return j-i+1;
}
static int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2;
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
static int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2;
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
public static void main(String args[])
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3;
int n = arr.length;
int c = count(arr, x, n);
System.out.println(x+" occurs "+c+" times");
}
}
|
Python3
def count(arr, x, n):
i = first(arr, 0, n-1, x, n)
if i == -1:
return i
j = last(arr, i, n-1, x, n);
return j-i+1;
def first(arr, low, high, x, n):
if high >= low:
mid = (low + high)//2
if (mid == 0 or x > arr[mid-1]) and arr[mid] == x:
return mid
elif x > arr[mid]:
return first(arr, (mid + 1), high, x, n)
else:
return first(arr, low, (mid -1), x, n)
return -1;
def last(arr, low, high, x, n):
if high >= low:
mid = (low + high)//2;
if(mid == n-1 or x < arr[mid+1]) and arr[mid] == x :
return mid
elif x < arr[mid]:
return last(arr, low, (mid -1), x, n)
else:
return last(arr, (mid + 1), high, x, n)
return -1
arr = [1, 2, 2, 3, 3, 3, 3]
x = 3
n = len(arr)
c = count(arr, x, n)
print ("%d occurs %d times "%(x, c))
|
C#
using System;
class GFG
{
static int count(int []arr, int x, int n)
{
int i;
int j;
i = first(arr, 0, n-1, x, n);
if(i == -1)
return i;
j = last(arr, i, n-1, x, n);
return j-i+1;
}
static int first(int []arr, int low, int high,
int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2;
if( ( mid == 0 || x > arr[mid-1])
&& arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
static int last(int []arr, int low,
int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2;
if( ( mid == n-1 || x < arr[mid+1])
&& arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
public static void Main()
{
int []arr = {1, 2, 2, 3, 3, 3, 3};
int x = 3;
int n = arr.Length;
int c = count(arr, x, n);
Console.Write(x + " occurs " + c + " times");
}
}
|
Javascript
<script>
function count(arr, x, n)
{
let i;
let j;
i = first(arr, 0, n - 1, x, n);
if (i == -1)
return i;
j = last(arr, i, n - 1, x, n);
return j - i + 1;
}
function first(arr, low, high, x, n)
{
if (high >= low)
{
let mid = (low + high) / 2;
if ((mid == 0 || x > arr[mid - 1]) &&
arr[mid] == x)
return mid;
else if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid - 1), x, n);
}
return -1;
}
function last(arr, low, high, x, n)
{
if (high >= low)
{
let mid = Math.floor((low + high) / 2);
if ((mid == n - 1 || x < arr[mid + 1]) &&
arr[mid] == x)
return mid;
else if (x < arr[mid])
return last(arr, low, (mid - 1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
let arr = [ 1, 2, 2, 3, 3, 3, 3 ];
let x = 3;
let n = arr.length;
let c = count(arr, x, n);
document.write(x + " occurs " + c + " times");
</script>
|
Output:
3 occurs 4 times
Time Complexity: O(Logn)
Auxiliary Space: O(1), as no extra space is used
Programming Paradigm: Divide & Conquer
Method 4 (Using Collections.frequency() method of java)
C++
#include <bits/stdc++.h>
using namespace std;
int countOccurrences(int arr[],
int x, int N)
{
int count = 0;
for (int i=0; i < N; i++)
if (arr[i] == x)
count++;
return count;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout <<x << " occurs "
<< countOccurrences(arr, x, N)
<< " times";
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.Collections;
public class GFG {
static int countOccurrences(ArrayList<Integer> clist,
int x)
{
return Collections.frequency(clist, x);
}
public static void main(String args[])
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
ArrayList<Integer> clist = new ArrayList<>();
for (int i : arr)
clist.add(i);
System.out.println(x + " occurs "
+ countOccurrences(clist, x)
+ " times");
}
}
|
Python3
def countOccurrences(arr, x) :
count = 0
n = len(arr)
for i in range(n) :
if (arr[i] == x):
count += 1
return count
if __name__ == "__main__":
arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ]
x = 2
print(x , "occurs"
, countOccurrences(arr, x)
, "times")
|
C#
using System;
public class GFG
{
static int countOccurrences(int[] arr,
int x)
{
int count = 0;
int n = arr.Length;
for (int i=0; i < n; i++)
if (arr[i] == x)
count++;
return count;
}
public static void Main (string[] args)
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
Console.WriteLine(x + " occurs "
+ countOccurrences(arr, x)
+ " times");
}
}
|
Javascript
<script>
function countOccurrences(arr, x)
{
let count = 0;
let n = arr.length;
for (let i=0; i < n; i++)
if (arr[i] == x)
count++;
return count;
}
let arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
let x = 2;
document.write(x + " occurs "
+ countOccurrences(arr, x)
+ " times");
</script>
|
Output:
2 occurs 4 times
Time Complexity: O(n)
Auxiliary Space: O(1), as no extra space is used
Method 5: Using Hashing
We can also use hashing method to count occurrences (or frequency) of a specific element in a sorted array.
Steps:
We use following steps to find occurrence-
- First we create an unsorted_map to store elements with their frequency.
- Now we iterate through the array and store its elements inside the map.
- Then by using map.find() function, we can easily find the occurrences (or frequency) of any element.
Below is the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int countOccurrences(int arr[], int x, int N)
{
unordered_map<int, int> mp;
for (int i = 0; i < N; i++) {
mp[arr[i]]++;
}
if (mp.find(x) == mp.end())
return 0;
auto it = mp.find(x);
return it->second;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout << x << " occurs " << countOccurrences(arr, x, N)
<< " times";
return 0;
}
|
Java
import java.util.HashMap;
import java.util.Map;
public class Main
{
static int countOccurrences(int[] arr, int x, int N)
{
Map<Integer, Integer> mp
= new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
}
if (!mp.containsKey(x))
return 0;
return mp.get(x);
}
public static void main(String[] args)
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
int N = arr.length;
System.out.println(x + " occurs "
+ countOccurrences(arr, x, N)
+ " times");
}
}
|
Python3
def countOccurrences(arr, x, N):
mp = {}
for i in range(N):
if arr[i] in mp:
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
if x not in mp:
return 0
return mp[x]
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
x = 2
N = len(arr)
print(x, "occurs", countOccurrences(arr, x, N), "times")
|
C#
using System;
using System.Collections.Generic;
class Program {
static int CountOccurrences(int[] arr, int x)
{
Dictionary<int, int> frequencyMap
= new Dictionary<int, int>();
foreach(int num in arr)
{
if (frequencyMap.ContainsKey(num))
frequencyMap[num]++;
else
frequencyMap[num] = 1;
}
int frequency;
if (frequencyMap.TryGetValue(x, out frequency))
return frequency;
else
return 0;
}
static void Main()
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
Console.WriteLine(x + " occurs "
+ CountOccurrences(arr, x)
+ " times");
}
}
|
Javascript
function countOccurrences(arr, x, N)
{
let mp = new Map();
for (let i = 0; i < N; i++) {
mp.set(arr[i], (mp.get(arr[i]) || 0) + 1);
}
if (!mp.has(x))
return 0;
return mp.get(x);
}
let arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8];
let x = 2;
let N = arr.length;
console.log(x + " occurs " + countOccurrences(arr, x,N) + " times");
|
Time Complexity: O(N), where N is the number of elements in the array.
Auxiliary Space: O(K), where K is the number of unique elements in the array.
Another Approach:
- For the first occurrence, we will first find the index of the number and then search again in the left subarray as long as we are finding the number.
- For the last occurrence, we will first find the index of the number and then search again in the right subarray as long as we are finding the number
Follow the steps mentioned below to implement the idea:
- Create a function search(int[] nums, int target, boolean findStartIndex) to find the index value of target.
- And for first occurrence set firstIndex = search(arr, target, true) and last occurrence set lastIndex = search(arr, target, false) and these function do following things:
? Set ans = -1 , start = 0 , end = arr.length – 1 .
? Iterate a loop while start <= end , such as:
? Set mid = start + (end – start) / 2 .
? Check if target < arr[mid] ,then set end = mid – 1.
? Else check if target > arr[mid], then set start = mid + 1.
? Otherwise , set ans = mid and check further such as
? If findStartIndex == true , then set end = mid – 1 .
? Else set start = mid + 1.
? Check if (firstIndex != -1 && lastIndex != -1 ) is true then return firstIndex- lastIndex +1 as the occurrences of x ,otherwise return 0.
Below is the implementation of the above approach:
C++
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int>& nums, int target, bool findStartIndex)
{
int answer = -1;
int start = 0;
int end = nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
answer = mid;
if (findStartIndex) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return answer;
}
int countOccurrences(vector<int>& nums, int x)
{
int firstIndex = search(nums, x, true);
int lastIndex = search(nums, x, false);
if (firstIndex != -1 && lastIndex != -1)
return lastIndex - firstIndex + 1;
else
return 0;
}
int main()
{
vector<int> arr{ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
int c = countOccurrences(arr, x);
cout << x << " occurs " << c << " times" << endl;
return 0;
}
|
C
#include <stdio.h>
int search(int nums[], int target, int findStartIndex, int length)
{
int answer = -1;
int start = 0;
int end = length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
answer = mid;
if (findStartIndex) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return answer;
}
int countOccurrences(int arr[], int length, int x)
{
int firstIndex = search(arr, x, 1, length);
int lastIndex = search(arr, x, 0, length);
if (firstIndex != -1 && lastIndex != -1)
return lastIndex - firstIndex + 1;
else
return 0;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
int c = countOccurrences(arr, n, x);
printf("%d occurs %d times\n", x, c);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int count(int arr[], int x)
{
int firstIndex = search(arr, x, true);
int lastIndex = search(arr, x, false);
if (firstIndex != -1 && lastIndex != -1)
return lastIndex - firstIndex + 1;
else
return 0;
}
static int search(int[] nums, int target,
boolean findStartIndex)
{
int ans = -1;
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
ans = mid;
if (findStartIndex) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = arr.length;
int x = 2;
int c = count(arr, x);
System.out.println(x + " occurs " + c + " times");
}
}
|
Python3
def count(nums, target):
first_index = search(nums, target, True)
last_index = search(nums, target, False)
if first_index != -1 and last_index != -1:
return last_index - first_index + 1
else:
return 0
def search(nums, target, find_start_index):
ans = -1
start = 0
end = len(nums) - 1
while start <= end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid - 1
elif target > nums[mid]:
start = mid + 1
else:
ans = mid
if find_start_index:
end = mid - 1
else:
start = mid + 1
return ans
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
x = 2
c = count(arr, x)
print(f"{x} occurs {c} times")
|
C#
using System;
public class GFG {
static int Count(int[] arr, int x)
{
int firstIndex = Search(arr, x, true);
int lastIndex = Search(arr, x, false);
if (firstIndex != -1 && lastIndex != -1)
return lastIndex - firstIndex + 1;
else
return 0;
}
static int Search(int[] nums, int target,
bool findStartIndex)
{
int ans = -1;
int start = 0;
int end = nums.Length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
ans = mid;
if (findStartIndex) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return ans;
}
public static void Main()
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = arr.Length;
int x = 2;
int c = Count(arr, x);
Console.WriteLine(x + " occurs " + c + " times");
}
}
|
Javascript
function count(arr, x) {
const firstIndex = search(arr, x, true);
const lastIndex = search(arr, x, false);
if (firstIndex !== -1 && lastIndex !== -1)
return lastIndex - firstIndex + 1;
else
return 0;
}
function search(nums, target, findStartIndex) {
let ans = -1;
let start = 0;
let end = nums.length - 1;
while (start <= end) {
let mid = start + Math.floor((end - start) / 2);
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
start = mid + 1;
}
else {
ans = mid;
if (findStartIndex) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
}
return ans;
}
const arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8];
const x = 2;
const c = count(arr, x);
console.log(x + " occurs " + c + " times");
|
Time Complexity: O(log n)
Auxiliary Space: O(1)
Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...