How to check for Majority Element in a sorted array in Python

In this tutorial, we are going to learn how to check whether the given element is the majority element or not in the given sorted array in Python.

First of all, we will learn what is Majority element, a majority element is an element that occurs more than N/2 times( N is the array size).
Given a sorted integer array, and target element. if the target number is the majority number it returns True, otherwise False.

We will take an array:

array[]={1,3,5,5,5,5,6}

Target element=5
Result= True(5 occurs more than N/2 times)

we will take another example

array[]={1,1,3,3,4,4,5,5,6}
Target element=5.
Result= False(5 does not occur more than N/2 times)

Methods to Find the Majority Element

1. Linear search.
2.  Binary search.

By Implementing a linear search in Python to check the majority element

def mjElement(array, n, a): 
  
  high = (n//2 + 1) if n % 2 == 0 else (n//2) 

  for i in range(high): 
    
    if array[i] == a and array[i + n//2] == a: 
      return 1

 
arr = [1, 2, 3, 5, 5, 5, 5] 
n = len(array) 
a = 5
if (mjElement(array, n, a)): 
  print ("false: %d is not a mority element") 
else: 
  print ("true": %d is a mojarity element) 


 

true: 5 is a mojarity element

Now we will implement it using binary search

By Implementing Binary search in Python to check the majority element

def mjElement(array, n, a): 
  
  
  i = _binarySearch(array, 0, n-1, a) 

  
  if i == -1: 
    return False

  if ((i + n//2) <= (n -1)) and arr[i + n//2] == a: 
    return True
  else: 
    return False


def _binarySearch(array, low, high, a): 
  if high >= low: mid = (low + high)//2 # low + (high - low)//2; 

    
    if (mid == 0 or a > array[mid-1]) and (array[mid] == a): 
      return mid 
    elif x > arr[mid]: 
      return _binarySearch(array, (mid + 1), high, a) 
    else: 
      return _binarySearch(array, low, (mid -1), a) 
  return -1


array = [1, 2, 1, 1, 1, 3, 10] 
n = len(array) 
a = 10
if (mjElement(array, n, a)): 
  print ("True:%d  a majority element") 
else: 
  print ("false: %d is not a majority element")

In the above code, 10 appears only once so the code gives the output as 10 is not a majority element.

false:10 is not a majority element

How to find a majority element in an Unsorted List in Python