题解 | 小红的顺子

import sys
import bisect

n = int(input())
nums = list(map(int, input().split()))
# res = 0
# cur = 1
# last = nums[0]
# for x in nums:
#     if x - last == 1:
#         cur += 1
#         if cur > res:
#             res = cur
#     else:
#         cur = 1
#     last = x
    
# print(res)

nums.append(n+1)

l = 0
r = n - 1
while l<r:
    mid = (l+r)//2
    if nums[mid] - mid==1:
        l = mid + 1
    elif nums[mid] - mid==2:
        r = mid

res = nums[r] - 2
print(max(res, n-1-res))

二分法，数字比序号大1，说明缺少数字在右侧，否则说明在左侧。

复杂度：log(n)