python实现leetcode之81. 搜索旋转排序数组 II

解题思路

在旋转数组中找
先对比中间元素

如果等于目标值，再看看左边有没有，有就返回出现最早的下标，没有就返回中间下标
如果不等于目标值，看数组区间是不是旋转的

如果是，再看目标值与中间值的关系

小于中间值：一定在左边
大于中间值：可能在左边，也可能在右边

如果两端元素值相等

可能旋转也可能不旋转，所以，左右都看看

如果非降序

使用常规的二分查找，但是找最小下标即可

81. 搜索旋转排序数组 II

代码

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        return rotated_search(arr, 0, len(arr)-1, target) != -1


def rotated_search(arr, low, high, target):
    """
    在带重复的旋转数组里面搜索
        如果搜索到，返回最小下标
        否则，返回-1
    """
    if low > high: return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return vmin(rotated_search(arr, low, mid-1, target), mid)
    if arr[low] > arr[mid]:   # 左半边有最大值和最小值，右半边是有序的
        if target < arr[mid]:
            return rotated_search(arr, low, mid-1, target)
        else:
            return vmin(
                rotated_search(arr, low, mid-1, target),
                rotated_search(arr, mid+1, high, target))
    elif arr[low] == arr[mid]:
        return vmin(
            rotated_search(arr, low+1, mid-1, target),
            rotated_search(arr, mid+1, high, target))
    else:  # arr[low] < arr[mid]
        if target < arr[low]:
            return rotated_search(arr, mid+1, high, target)
        else:
            return vmin(
                rotated_search(arr, low, mid-1, target),
                rotated_search(arr, mid+1, high, target))


def vmin(x, y):
    # -1代表没有找到
    if x == -1: return y
    if y == -1: return x
    return min(x, y)