LeetCode——搜索旋转排序数组

偏执的太偏执、 2022-05-16 12:19 204阅读 0赞

**题目**：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]` )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 `-1` 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 *O*(log *n*) 级别。

**示例 1:**

输入: nums = [4,5,6,7,0,1,2], target = 0
    输出: 4

**示例 2:**

输入: nums = [4,5,6,7,0,1,2], target = 3
    输出: -1

**思想**：

看到时间复杂度，我们首先想到的是二分查找，这里也是一样的，只不过条件需要变化一下，在原版二分查找里，mid的两边都是有序的，但是这题目中是mid至少有一边是有序的，有可能左边，有可能右边，有可能都是有序的，我们在有序的一遍查找，然后判断target是在有序的一遍还是无序的那一边。

**代码**：

class Solution:
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if len(nums) == 0:
                return -1
            if len(nums) == 1:
                if target == nums[0]:
                    return 0
                else:
                    return -1
            left = 0
            right = len(nums) - 1
            mid = 0
            while left <= right:
                mid = int((left + right)/2)
                if target == nums[mid]:
                    return mid
                if nums[mid] >= nums[left]:#左边有序
    
                    if target < nums[mid] and target >= nums[left]:#在有序的一遍
                        right = mid-1
                    else:#在无序的那边
                        left = mid +1
                else:#右边有序
                    if target > nums[mid] and target <= nums[right]:
                        left = mid+1
                    else:
                        right = mid -1
            return -1