-
Notifications
You must be signed in to change notification settings - Fork 41
/
solution.py
55 lines (53 loc) · 1.54 KB
/
solution.py
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
L = mountain_arr.length()
# 找到峰顶
peakIndex = 0
low = 0
high = L-1
while low<=high :
mid = (low+high)//2
midVal = mountain_arr.get(mid)
rightVal = mountain_arr.get(mid+1)
if midVal < rightVal :
low = mid+1
else :
leftVal = mountain_arr.get(mid-1)
if midVal>leftVal :
peakIndex = mid
break
else :
high = mid-1
# 在左边找
low = 0
high = peakIndex-1
while low<=high:
mid = (low+high)//2
midVal = mountain_arr.get(mid)
if midVal == target :
return mid
elif midVal<target:
low = mid+1
else :
high = mid-1
# 在右边找
low = peakIndex
high = L-1
while low<=high:
mid = (low+high)//2
midVal = mountain_arr.get(mid)
if midVal == target :
return mid
elif midVal<target :
high = mid-1
else :
low = mid+1
# 都没有
return -1