Find element in a sorted array whose frequency is greater than or equal to n/2.
Given a sorted array of length n, find the number in array that appears more than or equal to n/2 times. It is given that such element always exists.
Examples:
Input : 2 3 3 4 Output : 3 Input : 3 4 5 5 5 Output : 5 Input : 1 1 1 2 3 Output : 1
To find that number, we traverse the array and check the frequency of every element in array if it is greater than or equals to n/2 but it requires extra space and time complexity will be O(n).
But we can see that the if there is number that comes more than or equal to n/2 times in a sorted array, then that number must be present at the position n/2 i.e. a[n/2].
Implementation:
C++
// C++ code to find majority element in a // sorted array #include <iostream> using namespace std; int findMajority( int arr[], int n) { return arr[n / 2]; } int main() { int arr[] = { 1, 2, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findMajority(arr, n); return 0; } |
Java
// Java code to find majority element in a // sorted array public class Test { public static int findMajority( int arr[], int n) { return arr[n / 2 ]; } public static void main(String args[]) { int arr[] = { 1 , 2 , 2 , 3 }; int n = arr.length; System.out.println(findMajority(arr, n)); } } |
Python 3
# Python 3 code to find # majority element in a # sorted array def findMajority(arr, n): return arr[ int (n / 2 )] # Driver Code arr = [ 1 , 2 , 2 , 3 ] n = len (arr) print (findMajority(arr, n)) # This code is contributed by Smitha. |
C#
// C# code to find majority element in a // sorted array using System; public class GFG { public static int findMajority( int []arr, int n) { return arr[n / 2]; } // Driver code public static void Main() { int []arr = { 1, 2, 2, 3 }; int n = arr.Length; Console.WriteLine(findMajority(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP code to find majority // element in a sorted array function findMajority( $arr , $n ) { return $arr [ intval ( $n / 2)]; } // Driver Code $arr = array (1, 2, 2, 3); $n = count ( $arr ); echo findMajority( $arr , $n ); // This code is contributed by Sam007 ?> |
Javascript
<script> // Javascript code to find majority element in a // sorted array function findMajority(arr, n) { return arr[(Math.floor(n / 2))]; } // driver code let arr = [ 1, 2, 2, 3 ]; let n = arr.length; document.write(findMajority(arr, n)); </script> |
Output
2
Time Complexity : O(1)
Auxiliary Space: O(1)
Related Articles :
Majority element in an unsorted array
Check for majority element in a sorted array
Contact Us