fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. // Function to find first or last occurrence of a given number in
  4. // sorted array of integers. If searchFirst is true, we return the
  5. // first occurrence of the number else we return its last occurrence
  6. int BinarySearch(int A[], int N, int x, int searchFirst)
  7. {
  8.     // search space is A[low..high]
  9.     int low = 0, high = N - 1;
  10.  
  11.     // initialize the result by -1
  12.     int result = -1;
  13.  
  14.     // iterate till search space contains at-least one element
  15.     while (low <= high)
  16.     {
  17.         // find the mid value in the search space and
  18.         // compares it with target value
  19.         int mid = (low + high)/2;
  20.  
  21.         // if target is found, update the result
  22.         if (x == A[mid])
  23.         {
  24.             result = mid;
  25.  
  26.             // go on searching towards left (lower indices)
  27.             if (searchFirst)
  28.                 high = mid - 1;
  29.  
  30.             // go on searching towards right (higher indices)
  31.             else
  32.                 low = mid + 1;
  33.         }
  34.  
  35.         // if target is less than the mid element, discard right half
  36.         else if (x < A[mid])
  37.             high = mid - 1;
  38.  
  39.         // if target is more than the mid element, discard left half
  40.         else
  41.             low = mid + 1;
  42.     }
  43.  
  44.     // return the found index or -1 if the element is not found
  45.     return result;
  46. }
  47.  
  48. // Count occurrences of a number in a sorted array with duplicates
  49. int main(void)
  50. {
  51.     int A[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
  52.     int target = 5;
  53.  
  54.     int n = sizeof(A)/sizeof(A[0]);
  55.     int first = BinarySearch(A, n, target, 1);  // 1 for first occurrence
  56.     int last = BinarySearch(A, n, target, 0);   // 0 for last occurrence
  57.  
  58.     int count = last - first + 1;
  59.  
  60.     if (first != -1)
  61.         printf("Element %d occurs %d times.", target, count);
  62.     else
  63.         printf("Element not found in the array.");
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Element 5 occurs 3 times.
https://ideone.com/NmcBiq
Count occurrences of a number in a sorted array with duplicates
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

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!