Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一个递增的数组从中间切断,前面一半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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理