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.
/* * Java Program to Find the Number of occurrences of a given Number using Binary Search approach */ import java.util.Scanner; public class NumberOfOccurences { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Enter number of elements in sorted array"); int N = scan.nextInt(); int[] arr = new int[ N ]; /* Accept N elements */ System.out.println("Enter "+ N +" sorted elements"); for (int i = 0; i < N; i++) arr[i] = scan.nextInt(); System.out.println("Enter number to find occurences"); int num = scan.nextInt(); int f = occur(arr, num); if (f == -1) System.out.println("No occurence"); else System.out.println("Occurences = "+ f); } public static int occur(int[] arr, int num) { /* find first index */ int l1 = first(arr, num); /* find last index */ int l2 = last(arr, num); if (l1 == -1 || l2 == -1) return -1; return l2 - l1 + 1; } public static int first(int[] arr, int num) { if (arr[0] == num) return 0; int start = 0, end = arr.length - 1; int mid = (start + end) / 2; int flag = 0; while (!(arr[mid] == num && arr[mid - 1] < arr[mid])) { if (start == end) { flag = 1; break; } if (arr[mid] >= num) end = mid - 1; if (arr[mid] < num) start = mid + 1; mid = (start + end) / 2; } if (flag == 0) return mid; return -1; } public static int last(int[] arr, int num) { if (arr[arr.length - 1] == num) return arr.length - 1; int start = 0, end = arr.length - 1; int mid = (start + end) / 2; int flag = 0; while (!(arr[mid] == num && arr[mid + 1] > arr[mid])) { if (start == end) { flag = 1; break; } if (arr[mid] > num) end = mid - 1; if (arr[mid] <= num) start = mid + 1; mid = (start + end) / 2; } if (flag == 0) return mid; return -1; } }
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
Related posts:
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Serialize Only Fields that meet a Custom Criteria with Jackson
Spring Security Form Login
String Operations with Java Streams
Spring Boot - Tomcat Deployment
The Order of Tests in JUnit
Custom Cascading in Spring Data MongoDB
New Features in Java 12
Debugging Reactive Streams in Java
Java Program to Implement Insertion Sort
Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph
New Features in Java 11
Spring Security Remember Me
Java Program to Describe the Representation of Graph using Adjacency Matrix
Spring Security Basic Authentication
Adding Shutdown Hooks for JVM Applications
Reversing a Linked List in Java
Concurrent Test Execution in Spring 5
Java Program to Implement Word Wrap Problem
Using JWT with Spring Security OAuth (legacy stack)
HashSet trong Java hoạt động như thế nào?
Java Program to Perform Polygon Containment Test
Java Program to Implement Miller Rabin Primality Test Algorithm
Đồng bộ hóa các luồng trong Java
Simplify the DAO with Spring and Java Generics
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Introduction to Java Serialization
The Basics of Java Security
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Reactive WebSockets with Spring 5
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Java Program to Implement Expression Tree