LeetCode/SearchInRotatedSortedArray.py at master · git-babel/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
"""
If you divide list in half, one of two is strictly increasing, by description.
If target is in increasing range, recursively search in that one.
Else, search in the other one.
"""

class Solution:
    def _search(self, nums: List[int], target: int, start: int, end: int):
        if end - start < 0:
            return -1

        if start == end:
            if nums[start] == target:
                return start
            else:
                return -1

        pivot = start + (end - start) // 2
        l = nums[start]
        r = nums[end]

        if nums[pivot] == target:
            return pivot
        elif l <= nums[pivot]:
            if nums[pivot] > target and l <= target:
                return self._search(nums, target, start, pivot-1)
            else:
                return self._search(nums, target, pivot+1, end)
            elif nums[pivot] <= r:
                if nums[pivot] < target and r >= target:
                    return self._search(nums, target, pivot+1, end)
            else:
                return self._search(nums, target, start, pivot-1)

    def search(self, nums: List[int], target: int) -> int:
        return self._search(nums,  target, 0, len(nums) - 1)