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:

Java Program to Implement Double Ended Queue
Java Program to Describe the Representation of Graph using Adjacency List
Giới thiệu Java Service Provider Interface (SPI) – Tạo các ứng dụng Java dễ mở rộng
Java Program to Implement Gauss Seidel Method
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Java Program to Implement Solovay Strassen Primality Test Algorithm
Custom Error Pages with Spring MVC
Get the workstation name or IP
Java Program to Implement Sorted List
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Spring Cloud – Bootstrapping
How to Store Duplicate Keys in a Map in Java?
Java Program to Implement Suffix Tree
Comparing Strings in Java
Guide to the Synchronized Keyword in Java
Java Program to Implement ArrayBlockingQueue API
Java NIO2 Path API
The “final” Keyword in Java
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java
Spring Cloud – Securing Services
Java Program to Implement Efficient O(log n) Fibonacci generator
Java Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected
Getting Started with Custom Deserialization in Jackson
Hướng dẫn Java Design Pattern – Composite
Iterating over Enum Values in Java
Get and Post Lists of Objects with RestTemplate
Java Program to Implement Insertion Sort
Netflix Archaius with Various Database Configurations
Spring Boot - Creating Docker Image
Java Program to Implement the Program Used in grep/egrep/fgrep