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:
How to Replace Many if Statements in Java
Check If Two Lists are Equal in Java
Using the Map.Entry Java Class
Connect through a Proxy
Luồng Daemon (Daemon Thread) trong Java
Java Program to Implement HashSet API
Java Program to Implement DelayQueue API
Java – Combine Multiple Collections
Introduction to Spring Data JPA
JWT – Token-based Authentication trong Jersey 2.x
Giới thiệu Java 8
Convert XML to JSON Using Jackson
Request a Delivery / Read Receipt in Javamail
Java Program to Solve a Matching Problem for a Given Specific Case
Sử dụng CountDownLatch trong Java
Hướng dẫn Java Design Pattern – Transfer Object
Lớp Collectors trong Java 8
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Partition a List in Java
Simplify the DAO with Spring and Java Generics
Kết hợp Java Reflection và Java Annotations
Java Program to Generate N Number of Passwords of Length M Each
Java Program to Implement Fibonacci Heap
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Java Program to Implement Interpolation Search Algorithm
So sánh ArrayList và LinkedList trong Java
Java Program to Implement Sparse Array
Creating a Custom Starter with Spring Boot
Use Liquibase to Safely Evolve Your Database Schema
Introduction to Java 8 Streams
Java Program to Implement Self organizing List
Lớp Collections trong Java (Collections Utility Class)