fork(115) download
  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
stdin
Standard input is empty
stdout
2
4
1
0