   # Given a sorted array, and given a number n, find number of times n occurs in the array using C in best possible way?

129 views
Given a sorted array, and given a number n, find number of times n occurs in the array using C in best possible way? posted Nov 11, 2016

+1 vote

I can share logic which will optimize little bit to solve this problem,

Let me divide the problem in 2 parts.

Considering Total number of elements in array is N, and key element searching is NUM, suppose it exists k times in the array.

1> Search the number and it's position in a SORTED ARRAY.
2> And getting the count of number of times the number exists.

Part 1: - Apply binary search on it and get the index where it is the number exist for this complexity will be log(N)
Part 2:- Then after getting the index where the number present,
Browse its left side till you get the same number
Browse its right side till you get the same number

So complexity K + log(N) in best/average cases , in worst case K count can be N also for all the array element is same and equal to the number you are searching for.

Example
0 1 2 3 4 5 6 7 8 9 10 (Index)
3 3 4 8 8 8 8 12 14 18 45
N = 11
Key = 8 i am searching for it
K = 4 as 8 is present 4 times.
Part 1 : Using binary search we can find that 8 is present at Index 5

Part 2:
Then go linearly towards Left side of index 5, till you get different number so here count will be 2
Then go linearly towards Right side of index 5, till you get different number so here count will be 1

So total count = 1+ 2 +1 = 4

Hope it is clear. answer Nov 15, 2016
nice approach
``````#include<stdio.h>
main()
{
int array,i,num,count=0;
for(i=0;i<10;i++)
{
printf("\nEnter array[%d] = ",i);
scanf("%d",&array[i]);
}
printf("Enter number to find occurance\n");
scanf("%d",&num);
for(i=0;i<10;i++)
{
if(array[i]==num)
count++;
}
if(count==0)
else
printf("%d is found %d times\n",num,count);
`````` answer Nov 11, 2016
Similar Questions

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.

Example : Array : 2,5,6,7,8,8,9
Target number : 5
Output : 5

Target number : 11
Output : 9

Target Number : 4
Output : 5