leetcode：1533. 找到最大整数的索引【奇特的二分】

题目截图

题目分析

• l, r, x, y从最大开始二分i和j
• 分奇数or偶数 关注mid 还是 mid + 1
• 考虑l, r, x, y = i, mid, mid(mid + 1), j
• 考虑compareSub(l, r, x, y)
• 若为1，大的在l, r 更新i j
• 若为-1，大的x, y 更新i j
• 若为0，mid在作怪
• 最后i < j -1即可，最后肯定在i j之中

ac code

# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader(object):
#	 # 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])
#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
#	 # Returns the length of the array
#    def length(self) -> int:
#


class Solution:
    def getIndex(self, reader: 'ArrayReader') -> int:
        n = reader.length()
        i, j = 0, n - 1
        while i < j - 1:
            mid = (i + j) // 2
            if (j - i) % 2 == 1:
                l, r, x, y = i, mid, mid + 1, j
            else:
                l, r, x, y = i, mid, mid, j
            res = reader.compareSub(l, r, x, y)
            if res == 1:
                i, j = l, r
            elif res == -1:
                i, j = x, y
            else:
                return mid # 相等必定mid搞事
        if reader.compareSub(i, i, j, j) == 1:
            return i
        return j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结

• 力扣会员题二分总爱出一些奇怪的交互
• 这里通过缩小和的范围，可以定位大的位置