Search in Rotated Sorted Array

发表于 | 分类于

[Leetcode] Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

解题思路：
判断目标数字和数组头尾的大小比较，然后根据比较结果，进行遍历，同时添加遍历退出的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if nums == None or len(nums) == 0:
            return -1

        if nums[0] <= target:
            for n in range(len(nums)):
                if target < nums[n]:
                    return -1
                if target == nums[n]:
                    return n
        elif nums[-1] >= target:
            for n in range(len(nums))[::-1]:
                if target > nums[n]:
                    return -1
                if target == nums[n]:
                    return n
        return -1