| 44 | |
| 45 | """ |
| 46 | class Solution(object): |
| 47 | def find_rotate(self, nums): |
| 48 | target = nums[0] |
| 49 | lo = 1 |
| 50 | |
| 51 | for i in range(1, len(nums)): |
| 52 | if nums[i] == target: |
| 53 | lo += 1 |
| 54 | else: |
| 55 | break |
| 56 | |
| 57 | hi = len(nums) |
| 58 | |
| 59 | while lo < hi: |
| 60 | mid = (lo + hi) // 2 |
| 61 | if nums[mid] > target: |
| 62 | lo = mid + 1 |
| 63 | else: |
| 64 | hi = mid |
| 65 | |
| 66 | return lo |
| 67 | |
| 68 | def bi_search(self, nums, target, lo, hi): |
| 69 | while lo < hi: |
| 70 | mid = (lo + hi) // 2 |
| 71 | if nums[mid] == target: |
| 72 | return mid |
| 73 | |
| 74 | if nums[mid] > target: |
| 75 | hi = mid |
| 76 | else: |
| 77 | lo = mid + 1 |
| 78 | |
| 79 | return -1 |
| 80 | |
| 81 | |
| 82 | def search(self, nums, target): |
| 83 | """ |
| 84 | :type nums: List[int] |
| 85 | :type target: int |
| 86 | :rtype: int |
| 87 | """ |
| 88 | if not nums: |
| 89 | return False |
| 90 | |
| 91 | rotate_index = self.find_rotate(nums) |
| 92 | |
| 93 | lo = 0 |
| 94 | hi = rotate_index |
| 95 | |
| 96 | one = self.bi_search(nums, target, lo, hi) |
| 97 | if one != -1: |
| 98 | return True |
| 99 | |
| 100 | two = self.bi_search(nums, target, hi, len(nums)) |
| 101 | if two != -1: |
| 102 | return True |
| 103 | return False |
nothing calls this directly
no outgoing calls
no test coverage detected