Find if any number appears more than n/4 times in a sorted array

I was asked the following in an interview:

Given a sorted array with n numbers (where n is a multiple of 4), return whether any number appears more than n/4 times.

My initial thought was to iterate over the array and keep a counter:

limit = len(nums) // 4
counter = 1

for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:
        counter += 1

        if counter > limit:
            return True
    else:
        counter = 1

return False

However the interviewer asked if I could do better. Sorted array, better than linear complexity, I immediately thought "binary search"... I explored this path but was clueless.

After a few minutes, he gave a hint: "if any i exists where nums[i] == nums[i + len(nums) / 4]", does that mean we should return true?

I was trying to apply this to my binary search and was not thinking straight so the hint went over my head... Retrospectively it is trivial, however I only see how to apply this with a sliding window:

limit = len(nums) // 4

for i in range(limit, len(nums)):
    if nums[i] == nums[i-limit]:
        return True

return False

Is it what the interviewer meant? Or is there a better, non-linear solution?

A number that appears more than n/4 times in nums must be one of the elements of nums[::len(nums)//4]. For each candidate number, we perform a binary search for the first position where it appears, and check whether the same number appears len(nums)//4 spots later:

import bisect
def check(nums):
    n = len(nums)
    assert n % 4 == 0

    for i in nums[::n//4]:
        first_appearance = bisect.bisect_left(nums, i)
        if first_appearance + n//4 < len(nums) and nums[first_appearance + n//4] == i:
            return True
    return False

We perform at most 4 binary searches, and at most a constant amount of other work, so the time complexity is O(log n).

Since the array is sorted, if a number appears more than n/4 times, it will span a block of length greater than n/4. Therefore, there will be at least one index i where the number at i is the same as the number at i + n/4.

Instead of iterating through every element, you can check positions spaced n/4 apart.

#Edited
def appears_more_than_n_over_4(nums):
  n = len(nums)
  limit = n // 4

  check_positions = [0, limit, 2 * limit, 3 * limit]

  for i in check_positions:
    # Find the start and end of the current element
    start = bisect.bisect_left(nums, nums[i])
    end = bisect.bisect_right(nums, nums[i]) - 1
    
    # Check if the count of the element exceeds the limit
    if end - start + 1 > limit:
        return True

 return False