一个递增的数组从中间切断,前面一半append到数组后面,问某个数target在不在数组内,二分,每次判断mid实在左边的那一段递增数组还是右边一段
1 #33
2 #Runtime: 19 ms (Beats 92.37%)
3 #Memory: 13.5 MB (Beats 57.32%)
4
5 class Solution(object):
6 def search(self, nums, target):
7 """
8 :type nums: List[int]
9 :type target: int
10 :rtype: int
11 """
12 l, r = 0, len(nums) - 1
13 while l <= r:
14 mid = (l + r) // 2
15 if nums[mid] == target:
16 return mid
17 if nums[mid] >= nums[0]:
18 if nums[0] <= target and nums[mid] > target:
19 r = mid - 1
20 else:
21 l = mid + 1
22 else:
23 if nums[mid] < target and nums[-1] >= target:
24 l = mid + 1
25 else:
26 r = mid - 1
27 return -1