算法题--在旋转过的有序数组里寻找指定元素

image.png

0. 链接

题目链接

1. 题目

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

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?

2. 思路1：二分查找变体

• 初始化 left = 0, right = len(nums) - 1
• 在循环每一步, 计算 mid = left + (right - left) // 2,
  • 如果target == nums[mid]， 则直接返回True
  • 如果nums[mid] < nums[left], 说明mid处于右半边, 则[mid, right]区间是有序的, 如果target处于这个区间, 则只需要left = mid + 1后在这个区间继续寻找了, 否则, 可以排除target处于[mid, right]的可能性, 则right = mid - 1后在mid以左寻找
  • 如果nums[mid] > nums[left], 说明mid处于左半边, 则[left, mid]区间是有序的, 如果target处于这个区间, 则只需要right = mid - 1后在这个区间继续寻找了, 否则, 可以排除target处于[left, mid]的可能性, 则left = mid + 1后在mid以右寻找
  • 无法判断mid处于哪个半边, 只好left += 1右移继续；所以此算法最坏情况时间复杂度是O(n)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if len(nums) == 0:
            return False

        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] < nums[left]:
                # mid处于右半边, 则[mid, right]是有序的
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            elif nums[mid] > nums[left]:
                # mid处于左半边, 则[left, mid]是有序的
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # mid和left元素相同, 此时无法分清mid到底处于左半边还是右半边, 只好让left往右移
                left += 1

        return False


def my_test(solution, nums, target):
    print('input: nums={}, target={}, \noutput: {}'.format(nums, target, solution.search(nums, target)))
    print('=' * 50)


solution = Solution()
my_test(solution, [2, 5, 6, 0, 0, 1, 2], 0)
my_test(solution, [2, 5, 6, 0, 0, 1, 2], 3)
my_test(solution, [], 5)
my_test(solution, [1, 3], 3)
my_test(solution, [1, 1, 3], 3)
my_test(solution, [1, 1, 5], 1)
my_test(solution, [1, 3, 1, 1, 1], 3)

输出结果

input: nums=[2, 5, 6, 0, 0, 1, 2], target=0, 
output: True
==================================================
input: nums=[2, 5, 6, 0, 0, 1, 2], target=3, 
output: False
==================================================
input: nums=[], target=5, 
output: False
==================================================
input: nums=[1, 3], target=3, 
output: True
==================================================
input: nums=[1, 1, 3], target=3, 
output: True
==================================================
input: nums=[1, 1, 5], target=1, 
output: True
==================================================
input: nums=[1, 3, 1, 1, 1], target=3, 
output: True
==================================================

4. 结果

image.png