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

Question

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.

Answer 1

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.

Comments

nice approach

Answer 2

#include<stdio.h>
main()
{
        int array[10],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)
                printf("%d is not found\n",num);
        else
                printf("%d is found %d times\n",num,count);