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 Basis and Dimension of a Matrix
The HttpMediaTypeNotAcceptableException in Spring MVC
Chuyển đổi giữa các kiểu dữ liệu trong Java
Service Registration with Eureka
Chương trình Java đầu tiên
Jackson – Change Name of Field
Netflix Archaius with Various Database Configurations
Primitive Type Streams in Java 8
A Guide to @RepeatedTest in Junit 5
Practical Java Examples of the Big O Notation
Java Program to Encode a Message Using Playfair Cipher
Posting with HttpClient
Spring Security Basic Authentication
Vòng lặp for, while, do-while trong Java
Java Program to Implement Fibonacci Heap
How to Replace Many if Statements in Java
Guide to Spring Cloud Kubernetes
Quick Guide to Spring MVC with Velocity
Java Program to Implement Bresenham Line Algorithm
Jackson vs Gson
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Static Content in Spring WebFlux
Spring Data Reactive Repositories with MongoDB
Java Program to Implement RoleUnresolvedList API
Lớp Collections trong Java (Collections Utility Class)
Spring Boot - Google Cloud Platform
Spring Cloud AWS – RDS
Spring @RequestParam Annotation
Spring Security OAuth Login with WebFlux
Java Program to Implement Sorted List
Hướng dẫn Java Design Pattern – Strategy
Java Program to Implement Maximum Length Chain of Pairs