CODEWITHSUNDEEP
c++arraysbinary-search
Mateusz Młodochowski
Mateusz Młodochowski

Reputation: 11

Function to count same numbers in array C++

I have this function that is supposed to count how many duplicates of same number occur in certain array. Important this must be of complexity O(logn). I wrote this one below, but it doesn't count the duplicates properly. Also one more thing, the numbers are sorted from lowest to highest.

int CountElementsinFile(int *Arr, int num, int numOfD)
{
    int avg{}; 
    int inB = 0; 
    int inE = numOfD - 1; 
    int el{};
    while (inB <= inE)
    {
        avg = (inB + inE) / 2;

        if (Arr[avg] == num)
            el++;
            if (Arr[avg] > num)
                inE = avg - 1;
            else
                inB = avg + 1;
    }

    return el;
}

Upvotes: 1

Views: 405

Answers (4)

Dmytro Dadyka
Dmytro Dadyka

Reputation: 2260

You need to determine the upper and lower boundaries of num subsequence using the Bisection method. You need to rearrange the lower or upper (depending on the comparison) search region boundary in the while loop until inB < inE reducing the region in half. The complexity will be O(ln(n)). You were close, but you will not be able to find both boundaries in one while loop. I just corrected your code.

int CountElementsinFile(int *Arr, int num, int numOfD)
{
   // There is no num in the array
   if (Arr[0] > num || Arr[numOfD - 1] < num)
      return 0;

   int avg{};
   int lb, ub;

   // Find lower boundary
   int inB = 0;
   int inE = numOfD - 1;
   while (inB < inE)
   {
      // divide search region
      avg = (inB + inE) / 2;
      if (Arr[avg] >= num)
         inE = avg;
      else
         inB = avg+1;
   }

   lb = inE;

   // Find upper boundary   
   // inB already found
   inE = numOfD - 1;
   while (inB < inE)
   {
      avg = (inB + inE + 1) / 2;
      if (Arr[avg] > num)
         inE = avg-1;
      else
         inB = avg;
   }

   ub = inB;

   return ub - lb + 1;
}

int main()
{
   int arr[] = { 5, 7, 8, 9, 9, 9, 9, 9, 11 };
   std::cout << CountElementsinFile(arr, 9, sizeof(arr) / sizeof(int)) << std::endl;
   return 0;
}

Upvotes: 2

poojakz
poojakz

Reputation: 47

#include<algorithm>
using namespace std;

int CountElementsinFile(int arr[], int size, int numToSearch)
{
    return count(arr, arr + size, numToSearch); 
}

Upvotes: 0

Botje
Botje

Reputation: 30860

From the function signature you gave, I am guessing you were given a number N and a sorted array of numbers and need to count how many times N appears in the array.

Since the array is sorted, you need to find the index (using binary search) of the first number that is smaller than N (this is O(log n)), the index of the first number larger than N (this is also O(log n)), and simply substract one index from the other. Of course you need to take into account edge cases where there are no numbers smaller than N or larger than N, but that is for you to figure out.

Upvotes: 0

Jarod42
Jarod42

Reputation: 217478

With std, you might do:

int CountElementsinFile(const int *a, int size, int value)
{
    const auto range = std::equal_range(a, a + size, value);
    return range.second - range.first;
}

Upvotes: 2

Related Questions