Majority Element in a Sorted Array in Java?
Given a sorted array, we need to find if a given x is a majority element.
What is Majority element: Number occurring more than half the size of the array is called Majority element.
Lets understand with the help of example below,
Algorithm
We will see two solutions one having time complexity O(N) and one using Binary Search approach having time complexity O(log N).
As the array is sorted we can use binary search to find the index of first occurrence of element to search and once that is found, we can directly add n/2 in that index to see if that index also contains the same element as element to search and if yes, then we have majority element else not.
package com.javabypatel.arrays;
public class MajorityOfElementInSortedArray {
public static void main(String[] args) {
int arr[];
//arr = new int[] {1, 2, 2, 2, 3, 3, 3};
//arr = new int[] {1, 1, 1, 2, 2, 3};
//arr = new int[] {1, 1, 1, 2, 2, 2, 2};
//arr = new int[] {2, 2};
arr = new int[] {2};
int x = 3;
boolean result = isMajority(x, arr, arr.length);
System.out.println(result);
result = isMajorityUsingBinarySearch(x, arr, arr.length);
System.out.println(result);
}
//Time complexity O(N)
private static boolean isMajority(int elementToSearch, int[] arr, int length) {
//Here we are calculating till what index we need to search for element.
//we need to only search till length/2 index for even length array and length/2+1 for odd length array after that index if element is present/absent
//doesn't matter as count of the element would not be greater than length/2+1 after crossing middle element.
int searchUptil = length % 2 == 0 ? length / 2 : length / 2 + 1;
for (int i = 0; i < searchUptil; i++) {
//If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
//if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
if(arr[i] == elementToSearch && arr[i + arr.length/2] == elementToSearch) {
return true;
}
}
return false;
}
private static boolean isMajorityUsingBinarySearch(int elementToSearch, int[] arr, int length) {
return isMajorityHelper(elementToSearch, arr, 0, length-1);
}
/*
In this approach we will find the first instance of the elementToSearch using BinarySearch after that
we will directly check the index n/2 from that point and if it is same as elementToSearch then we have
n/2 count of elementToSearch else not.
*/
static boolean isMajorityHelper(int elementToSearch, int[] arr, int start, int end) {
if (start > end) {
return false;
}
int mid = start + (end - start) / 2;
if (arr[mid] == elementToSearch && (mid == 0 || arr[mid-1] < elementToSearch)) {
//If we get the index of the first match elementToSearch then check the value at the (currentIndex + length/2)
//if the value at that index is elementToSearch then elementToSearch occur more than length/2 times.
if((mid + arr.length/2 < arr.length) && arr[mid + arr.length/2] == elementToSearch) {
return true;
}
return false;
} else if (arr[mid] < elementToSearch) {
//Search on right side of mid.
return isMajorityHelper(elementToSearch, arr, mid + 1, end);
} else {
//if the elementToSearch is found and is not the first instance or
//if elementToSearch is greater than mid, continue searching on left side of mid.
return isMajorityHelper(elementToSearch, arr, start, mid - 1);
}
}
}
You may also like to see
Advanced Java Multithreading Interview Questions & Answers
Type Casting Interview Questions and Answers In Java?
Exception Handling Interview Question-Answer
Method Overloading - Method Hiding Interview Question-Answer
How is ambiguous overloaded method call resolved in java?
Method Overriding rules in Java
Interface interview questions and answers in Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment