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:
A Quick JUnit vs TestNG Comparison
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Custom HTTP Header with the HttpClient
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Call Methods at Runtime Using Java Reflection
Java Program to Perform the Unique Factorization of a Given Number
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Java Program to Perform Left Rotation on a Binary Search Tree
Constructor Injection in Spring with Lombok
Spring Cloud AWS – Messaging Support
Java Program to Implement Dijkstra’s Algorithm using Queue
Tạo chương trình Java đầu tiên sử dụng Eclipse
Tạo ứng dụng Java RESTful Client với thư viện OkHttp
Java Program to Generate All Possible Combinations of a Given List of Numbers
Java Multi-line String
Java Program to Find a Good Feedback Edge Set in a Graph
Introduction to the Java NIO Selector
The StackOverflowError in Java
How to Get All Dates Between Two Dates?
Java Byte Array to InputStream
A Guide to Spring Cloud Netflix – Hystrix
Bootstrap a Web Application with Spring 5
Tính đóng gói (Encapsulation) trong java
Introduction to Project Reactor Bus
Java Program to Search for an Element in a Binary Search Tree
Java Program to Implement Levenshtein Distance Computing Algorithm
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Spring Boot Security Auto-Configuration
New Features in Java 8
Custom Cascading in Spring Data MongoDB
The Registration Process With Spring Security