Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
排序的数组里，找到那个出现次数超过1/4的数，保证只有一个。
n的做法可以是for一遍，然后比较arr[i] == arr[i + n // 4]
logn的做法，我们的候选数可能是出现在1/4 2/4 3/4这三个位置。二分一下这几个数在数组里的上下界，就得到了个数，判断一下。
class Solution(object): def findSpecialInteger(self, arr): """ :type arr: List[int] :rtype: int """ n = len(arr) candidates = [arr[n // 4], arr[n // 2], arr[n * 3 // 4]] for candidate in candidates: l = 0 r = n - 1 while l <= r: mid = (l + r) // 2 if arr[mid] < candidate: l = mid + 1 else: r = mid - 1 left_index = l l = 0 r = n - 1 while l <= r: mid = (l + r) // 2 if arr[mid] <= candidate: l = mid + 1 else: r = mid - 1 right_index = l if right_index - left_index > n // 4: return candidate