LeetCode 1533. Find the Index of the Large Integer（二分查找）

Example 1:
Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) 
// returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) 
// returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) 
// returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

Example 2:
Input: nums = [6,6,12]
Output: 2
 
Constraints:
2 <= arr.length <= 5 * 10^5
1 <= arr[i] <= 100
All elements of arr are equal except for one element which is larger than all other elements.

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     // Compares the sum of arr[l..r] with the sum of arr[x..y] 
 *     // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *     // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *     // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *     int compareSub(int l, int r, int x, int y);
 *
 *     // Returns the length of the array
 *     int length();
 * };
 */

class Solution {
public:
    int getIndex(ArrayReader &reader) {
        int n = reader.length(), l = 0, r = n-1, midl, midr;
        int flag;
        while(l < r)
        {
        	if((r-l)&1)//差为奇数
        		midl = (l+r)/2,
        		midr = (l+r)/2+1;
        	else//偶数
        		midl = midr = (l+r)/2;
        	flag = reader.compareSub(l, midl, midr,r);
        	if(flag > 0)//左边和大
        		r = midl;
        	else if(flag < 0)//右边和大
        		l = midr;
        	else//相等找到了
        		return midl;
        }
        return l;
    }
};