Java Program to Count Number of Occurrences of a Given Number using Binary Search

«
»
This is a Java Program to find number of occurences of a given number using binary search approach. The time complexity of the following program is O (log n).

Here is the source code of the Java program to find number of occurences of a given number using binary search approach. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *    Java Program to Find the Number of occurrences of a given Number using Binary Search approach
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. public class NumberOfOccurences
  8. {
  9.     public static void main(String[] args) 
  10.     {
  11.         Scanner scan = new Scanner(System.in);
  12.         System.out.println("Enter number of elements in sorted array");
  13.         int N = scan.nextInt();
  14.         int[] arr = new int[ N ];
  15.         /* Accept N elements */
  16.         System.out.println("Enter "+ N +" sorted elements");
  17.         for (int i = 0; i < N; i++)
  18.             arr[i] = scan.nextInt();
  19.         System.out.println("Enter number to find occurences");
  20.         int num = scan.nextInt();
  21.  
  22.         int f = occur(arr, num);
  23.         if (f == -1)
  24.             System.out.println("No occurence");
  25.         else 
  26.             System.out.println("Occurences = "+ f);
  27.     }    
  28.     public static int occur(int[] arr, int num)
  29.     {
  30.         /* find first index */
  31.         int l1 = first(arr, num);
  32.         /* find last index */
  33.         int l2 = last(arr, num);
  34.         if (l1 == -1 || l2 == -1)
  35.             return -1;
  36.         return l2 - l1 + 1;
  37.     }
  38.     public static int first(int[] arr, int num)
  39.     {
  40.         if (arr[0] == num)
  41.             return 0;
  42.         int start = 0, end = arr.length - 1;
  43.         int mid = (start + end) / 2;
  44.         int flag = 0;
  45.         while (!(arr[mid] == num && arr[mid - 1] < arr[mid]))
  46.         {
  47.             if (start == end)
  48.             {
  49.                 flag = 1;
  50.                 break;
  51.             }
  52.             if (arr[mid] >= num)
  53.                 end = mid - 1;
  54.             if (arr[mid] < num)
  55.                 start = mid + 1;
  56.             mid = (start + end) / 2;
  57.         }
  58.         if (flag == 0)
  59.             return mid;
  60.         return -1;        
  61.     }
  62.     public static int last(int[] arr, int num)
  63.     {
  64.         if (arr[arr.length - 1] == num)
  65.             return arr.length - 1;
  66.         int start = 0, end = arr.length - 1;
  67.         int mid = (start + end) / 2;
  68.         int flag = 0;
  69.         while (!(arr[mid] == num && arr[mid + 1] > arr[mid]))
  70.         {
  71.             if (start == end)
  72.             {
  73.                 flag = 1;
  74.                 break;
  75.             }
  76.             if (arr[mid] > num)
  77.                 end = mid - 1;
  78.             if (arr[mid] <= num)
  79.                 start = mid + 1;
  80.             mid = (start + end) / 2;
  81.         }
  82.         if (flag == 0)
  83.             return mid;
  84.         return -1;        
  85.     }
  86. }

advertisement
Enter number of elements in sorted array
10
Enter 10 sorted elements
1 1 3 3 3 3 4 4 4 5
Enter number to find occurences
3
Occurences = 4
 
 
Enter number of elements in sorted array
10
Enter 10 sorted elements
1 1 3 3 3 3 4 4 4 5
Enter number to find occurences
5
Occurences = 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.