fork(115) download
copy 
  1.  
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
  6.  
  7. // Input:       Indices Range [l ... r)
  8. // Invariant:   A[l] <= key and A[r] > key
  9. int GetRightPosition(int A[], int l, int r, int key) {
  10.     int m;
  11.  
  12.     while( r - l > 1 ) {
  13.         m = l + (r - l)/2;
  14.  
  15.         if( A[m] <= key )
  16.             l = m;
  17.         else
  18.             r = m;
  19.     }
  20.  
  21.     return l;
  22. }
  23.  
  24. // Input:       Indices Range (l ... r]
  25. // Invariant:   A[r] >= key and A[l] > key
  26. int GetLeftPosition(int A[], int l, int r, int key) {
  27.     int m;
  28.  
  29.     while( r - l > 1 ) {
  30.         m = l + (r - l)/2;
  31.  
  32.         if( A[m] >= key )
  33.             r = m;
  34.         else
  35.             l = m;
  36.     }
  37.  
  38.     return r;
  39. }
  40.  
  41. int CountOccurances(int A[], int size, int key) {
  42.     // Observe boundary conditions
  43.     int left  = GetLeftPosition(A, -1, size-1, key);
  44.     int right = GetRightPosition(A, 0, size, key);
  45.  
  46.     // What if the element doesn't exists in the array?
  47.     // The checks helps to trace that element exists
  48.     return (A[left] == key && key == A[right]) ? right - left + 1 : 0;
  49. }
  50.  
  51. int main() {
  52.     int A[] = {1, 1, 2, 2, 2, 2, 3};
  53.     int size = ARRAY_SIZE(A);
  54.  
  55.     int key;
  56.  
  57.     key = 1;
  58.     cout << CountOccurances(A, size , key) << endl;
  59.  
  60.     key = 2;
  61.     cout << CountOccurances(A, size , key) << endl;
  62.  
  63.     key = 3;
  64.     cout << CountOccurances(A, size , key) << endl;
  65.  
  66.     // Unsuccessful case
  67.     key = 4;
  68.     cout << CountOccurances(A, size , key) << endl;
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 2852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
4
1
0
https://ideone.com/zn6R6a
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!