一個遞增的數組從中間切斷，前面一半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