title: Find all elements that appear more than n/4 times in a sorted array
body: <p>My question is similar to <a href="https://stackoverflow.com/questions/24691048/find-all-elements-that-appear-more-than-n-4-times-in-linear-time">Find all elements that appear more than n/4 times in linear time</a>, you are given an array of size n, find all elements that appear more than n/4 times, the difference is that the array is sorted and the runtime should be better than O(n).</p>
  
  <p>My approach is to do 3 binary searches for the first occurrence of each element in position n/4, n/2 and 3*n/4, since the array is sorted, we can know if each element appears more than n/4 times by checking if the next n/4 element has the same value.</p>
  
  <p>I have written the following code in python3, do you guys think my approach is correct and if there is anything that can be simplified?:</p>
  
  <pre><code>import bisect
  
  # return -1 if x doesn't exist in arr
  def binary_search(arr, x):
      pos = bisect.bisect_left(arr, x)
      return pos if pos != len(arr) and arr[pos] == x else -1
  
  def majority(arr):
      n = len(arr)
      output = []
      quarters = [arr[n//4],arr[n//2],arr[3*n//4]]
  
      # avoid repeating answer in output array
      if arr[n//4] == arr[n//2]:
          quarters.remove(arr[n//4])
          quarters.remove(arr[n//2])
          output.append(arr[n//2])
      if arr[n//2] == arr[3*n//4]:
          if arr[n//2] in arr:
              quarters.remove(quarters[n//2])
          if arr[3*n//4] in arr:
              quarters.remove(quarters[3*n//4])
          if arr[n//2] not in output:
              output.append(arr[n//2])
  
      for quarter in quarters:
          pos = binary_search(arr, quarter)
          if pos != -1 and pos+n//4 &lt; len(arr) and arr[pos] == arr[pos+n//4]:
              output.append(arr[pos])
      return output
  
  print(majority([1,1,1,6,6,6,9,145]))
  </code></pre>