Java Program to find the number of occurrences of a given number using Binary Search approach

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:

Flattening Nested Collections in Java
Java Program to Represent Graph Using Adjacency List
Removing all duplicates from a List in Java
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Tính đa hình (Polymorphism) trong Java
Guide to Java 8 groupingBy Collector
Java Program to Perform Preorder Recursive Traversal of a Given Binary Tree
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Java Program to Implement Bresenham Line Algorithm
Java Program to Solve TSP Using Minimum Spanning Trees
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Tạo chương trình Java đầu tiên sử dụng Eclipse
Java Program to Implement CopyOnWriteArrayList API
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Sorting Query Results with Spring Data
Java Program to Implement WeakHashMap API
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Object Type Casting in Java
Spring Boot Integration Testing with Embedded MongoDB
Java Program to Compute Determinant of a Matrix
Java Map With Case-Insensitive Keys
So sánh ArrayList và LinkedList trong Java
Java Program to Implement Suffix Array
Explain about URL and HTTPS protocol
Java List UnsupportedOperationException
Java Program to Find Minimum Element in an Array using Linear Search
Java Program to Implement RenderingHints API
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Map Serialization and Deserialization with Jackson
Introduction to the Java NIO Selector
Java Multi-line String