Check If a Number Is Majority Element in a Sorted Array

class Solution {
public:
    int find_lower_bound(vector<int>& arr, int val) {
        int left = 0;
        int right = arr.size() - 1;
        int pos = arr.size();
        
        while (left <= right) {
            int middle = (left + right) / 2;
            
            if (arr[middle] >= val) {
                right = middle - 1;
                pos = middle;
            } else {
                left = middle + 1;
            }
        }
        
        return pos;
    }
    
    bool checkMajorityElement(vector<int>& arr, int val) {
        int firstPos = find_lower_bound(arr, val);
        
        return (firstPos + arr.size() / 2 < arr.size()) && (arr[firstPos + arr.size() / 2] == val);
    }
};

This C++ code implements a solution to determine if a number is the majority element in a sorted array. The provided C++ class Solution includes two main functions:

1. find_lower_bound:

   • This function computes the first position in the array where the value is greater than or equal to the target value val using a binary search algorithm. It adjusts the left, right, and middle indices based on the comparison between the middle element of the array and val. The function returns the lowest index pos where arr[pos] >= val.

2. checkMajorityElement:

   • This function first retrieves the lower bound position of val in the array using find_lower_bound.
   • Then, it checks if the element at the position half the size of the array away from this starting point is still equal to val. This verification along with the comparison of indices determines if val is the majority element in the array. The function returns true if val is the majority element, otherwise false.

The essence of the solution is in efficiently locating the start occurrence of the potential majority element using binary search and then verifying its dominance by checking its occurrence at the calculated majority position.

This implementation is optimized for a sorted array, ensuring that the check operation is done in logarithmic time. This is significantly faster than a linear scan, especially for large arrays.

class Solution {
    int findLowerBound(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;
        int result = array.length;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (array[mid] >= key) {
                right = mid - 1;
                result = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
    public boolean isMajorityElement(int[] array, int key) {
        int lowerIndex = findLowerBound(array, key);
        
        return lowerIndex + array.length / 2 < array.length && array[lowerIndex + array.length / 2] == key;
    }
}

The provided Java program checks if a given number is the majority element in a sorted array. A number is considered a majority element if it appears more than half the times in the sorted array. Here is the explanation and breakdown of how this validation is achieved:

• findLowerBound Method: Implements a binary search algorithm to find the lowest index (lowerIndex) of the given key within the array. It keeps adjusting the search range (left and right) and updates the result to the mid-point where the key is found or supposed to be inserted. This method returns the lowest index where the key could be inserted without disturbing the order of the sorted array, hence effectively giving the first occurrence of the key.

• isMajorityElement Method: Utilizes the findLowerBound method to get the lowerIndex of key in array. It checks whether adding half the length of the array to lowerIndex results in an index that still contains the key and compares whether this index doesn't exceed the boundary. If these conditions are true, key is the majority element and the method returns true. Otherwise, it returns false.

These methods together allow efficient checking of majority element presence by minimizing the need to iterate through the entire array, leveraging the property of binary search.