Find element in a sorted array whose frequency is greater than or equal to n/2.

Find Majority Element in a Sorted Array in Java? OR Find element in a sorted array whose frequency is greater than or equal to n/2.

---

Given a sorted array, find the number in array that appears more than or equal to n/2 times.
Condition: there will always be element which is repeated more than n/2 times.

Lets understand with the help of example below,

Try to solve the problem in less than O(1) complexity.

Algorithm

If the element is sorted and such element is always present which is repeated more than n/2 times in that case the repeated element must be the middle element of the array.

If the most repeated element is starting from 0th index, in that case it has to stretch till middle index then only it will be repeated n/2 times,

If the most repeated element is present at last index, if that is the case than middle index should also contain the same element than only it would have be repeated n/2 times,

If the most repeated starts some where in the middle in this case it is sure it would be passing from the middle index for having its count greater than or equal to n/2 times.

package com.javabypatel.arrays;

public class MajorityOfElementInSortedArray {

    public static void main(String args[]) {
        int arr[] = { 1, 2, 3, 3 };
        int n = arr.length;
        System.out.println(findMajorityElement(arr, n));
    }
    public static int findMajorityElement(int arr[], int n) {
        return arr[n / 2];
    }
}

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.