Solution Explanation for Check If a Number Is Majority Element in a Sorted Array

This problem asks to determine if a given target integer appears more than half the times in a sorted integer array nums. Leveraging the sorted nature of nums allows for efficient solutions using binary search.

Approach 1: Two Binary Searches

This approach performs two binary searches:

1. First Binary Search: Finds the index of the first occurrence of target (or the index where target would be inserted if it's not present). This is typically done using lower_bound (or its equivalent) in various languages.

2. Second Binary Search: Finds the index of the first occurrence of an element greater than target. This is done using upper_bound (or its equivalent).

The difference between the indices found in steps 1 and 2 represents the count of target in the array. If this count exceeds nums.length / 2, then target is a majority element.

Time Complexity: O(log n) due to the two binary searches. Binary search has logarithmic time complexity.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Approach 2: Optimized Single Binary Search

This approach refines the solution to only require a single binary search.

1. Binary Search: Perform a binary search to find the index (left) of the first occurrence of target.

2. Majority Check: Check if the element at index left + nums.length / 2 is equal to target. If it is, then target appears more than half the times, and it's a majority element. This cleverly avoids the second binary search. If the index left + nums.length / 2 goes beyond the array bounds, it implies that target cannot be a majority element.

Time Complexity: O(log n) because of the single binary search.

Space Complexity: O(1) as it uses constant extra space.

Code Implementation in Multiple Languages

The following code snippets demonstrate both approaches in several programming languages. Note that the specific functions for binary search might vary slightly depending on the language and library used (e.g., bisect_left, bisect_right in Python, lower_bound, upper_bound in C++, etc.).

Approach 1: Two Binary Searches

Python:

import bisect
 
class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left = bisect.bisect_left(nums, target)
        right = bisect.bisect_right(nums, target)
        return right - left > len(nums) // 2

Java:

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int left = binarySearch(nums, target);
        int right = binarySearch(nums, target + 1);
        return right - left > nums.length / 2;
    }
 
    private int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    bool isMajorityElement(std::vector<int>& nums, int target) {
        auto left = std::lower_bound(nums.begin(), nums.end(), target);
        auto right = std::upper_bound(nums.begin(), nums.end(), target);
        return std::distance(left, right) > nums.size() / 2;
    }
};

Approach 2: Optimized Single Binary Search

Python:

import bisect
 
class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left = bisect.bisect_left(nums, target)
        right = left + len(nums) // 2
        return right < len(nums) and nums[right] == target

Java: (Similar to Approach 1 Java, but the binarySearch function would be slightly adjusted to directly return the index)

C++: (Similar to Approach 1 C++, but the logic would be modified to reflect the single binary search approach).

The other languages (Go, TypeScript, etc.) can be implemented similarly, adapting the binary search techniques specific to those languages. The core logic remains consistent across all the languages, showcasing the elegance and efficiency of using binary search on sorted data.