Posted on 2023-10-12 21:31
Uriel 阅读(31)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
二分.三分
给出一个先单调上升后单调下降的数组，查询某个数，若不存在输出-1
先三分求极值，再分左右两段二分查找
1 #1095
2 #Runtime: 32 ms (Beats 61.2%)
3 #Memory: 14.5 MB (Beats 5.8%)
4
5 # """
6 # This is MountainArray's API interface.
7 # You should not implement it, or speculate about its implementation
8 # """
9 #class MountainArray(object):
10 # def get(self, index):
11 # """
12 # :type index: int
13 # :rtype int
14 # """
15 #
16 # def length(self):
17 # """
18 # :rtype int
19 # """
20
21 class Solution(object):
22 def findInMountainArray(self, target, mountain_arr):
23 """
24 :type target: integer
25 :type mountain_arr: MountainArray
26 :rtype: integer
27 """
28 def b_search(l, r, di):
29 while l < r:
30 mid = (l + r) // 2
31 if di == 0:
32 if mountain_arr.get(mid) < target:
33 l = mid + 1
34 else:
35 r = mid
36 else:
37 if mountain_arr.get(mid) > target:
38 l = mid + 1
39 else:
40 r = mid
41 return l
42
43 l, r = 0, mountain_arr.length() - 1
44 eps = 1e-6
45 while l < r:
46 mid = (l + r) // 2
47 midmid = (mid + r) // 2
48 if mountain_arr.get(mid) >= mountain_arr.get(midmid):
49 r = midmid
50 else:
51 l = mid + 1
52 idx = b_search(0, l, 0)
53 if mountain_arr.get(idx) == target:
54 return idx
55 idx = b_search(l + 1, mountain_arr.length() - 1, 1)
56 if mountain_arr.get(idx) == target:
57 return idx
58 return -1