题目：给定一个有序数组，返回其中出现次数超过25%的元素，题目确保有且仅有一个。
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6
分析：
方法一：遍历
时间复杂度为O(n)，空间复杂度为O(1)
int findSpecialInteger(vector<int>& arr) { int len = arr.size(); int step = len / 4; for(int i = 0;i + step < len;i++) { if(arr[i] == arr[i+step]) return arr[i]; } return -1; }
方法二：二分查找
根据题目要求，满足条件的整数 x 至少在数组 arr 中出现了 span = arr.length / 4 + 1 次，那么我们可以断定：数组 arr 中的元素 arr[0], arr[span], arr[span * 2], ... 一定包含 x。
因为连续span个数中，必然有一个span的倍数。
所以我们取间隔span的数去lower_bound和upper_bound查找，得到出现的次数。
int findSpecialInteger(vector<int>& arr) { int n = arr.size(); int step = n / 4 + 1; for(int i = 0;i < n; i += step) { vector<int>::iterator it_l = lower_bound(arr.begin(), arr.end(), arr[i]); vector<int>::iterator it_r = upper_bound(arr.begin(), arr.end(), arr[i]); if(it_r - it_l >= step) return arr[i]; } return -1; }
初看时间复杂度是O(nlogn)??
咋看，枚举的元素最多4个，所以时间复杂度为O(logn).