1class Solution:
2 def magicIndex(self, nums):
3 # return self.distinct(nums)
4 return self.notDistinct(nums, 0, len(nums) - 1)
5
6 def distinct(self, nums):
7 l, r = 0, len(nums) - 1
8
9 while l <= r:
10 middle = l + (r - l) // 2
11 if nums[middle] == middle: return middle
12 if nums[middle] < middle: l = middle + 1
13 else: r = middle - 1
14
15 return -1
16
17 def notDistinct(self, nums, l, r):
18 if r < l: return -1
19 middle = l + (r - l) // 2
20 if nums[middle] == middle: return middle
21
22 leftIndex = min(nums[middle], middle - 1)
23 left = self.notDistinct(nums, l, leftIndex)
24 if left >= 0: return left
25
26 rightIndex = max(middle + 1, nums[middle])
27 right = self.notDistinct(nums, rightIndex, r)
28 return right
29