本文共 1496 字，大约阅读时间需要 4 分钟。

给定一个没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-1），时间复杂度为logN。

• 查找3，返回-1；
• 查找0，返回4；

根据中位数与旋转点相对位置查找

从中位数与旋转点的相对位置看，可以有：

• 旋转点在中位数右侧：中位数及其左侧元素全部为升序，且小于中位数；
• 旋转点与中位数相同或在中位数左侧：中位数及其右侧元素全部升序，且大于中位数；

def searchInShiftArray(ary:list, ele:int)->int:    def bisearch(ary, start, end):        if start>end:            return -1        mid = (start+end)//2        if ary[mid] == ele:            return mid        if ary[mid]>ele:            return bisearch(ary, start, mid-1)        else:             return bisearch(ary, mid+1, end)    def search(ary, start, end):        if start>end:            return -1        mid = (start+end)//2        if ary[mid] == ele:            return mid        if ary[mid]
   
    ary[mid]: # mid在旋转点后，                if ary[end]>=ele:                    return bisearch(ary, mid+1, end)                return search(ary, start, mid-1)            # mid在旋转点前            return search(ary, mid+1, end)        else: # ary[mid]>ele            if ary[start]>ary[mid]: # mid在旋转点后，                return search(ary, start, mid-1)            # mid在旋转点前            if ary[start]<=ele:                return bisearch(ary, start, mid-1)            return search(ary, mid+1, end)    return search(ary, 0, len(ary)-1) 
   

切分数组查找

查找有序数组最方便的方式是二分查找，而旋转数组也可以看作是由‘旋转点’（数组中最小元素）切分的两个有序数组。可先找到旋转点，然后分别在两个有序数组中查找即可。

查找旋转点：

def findPivotPoint(ary:list)->tuple:    if ary[0]
   
    ary[end]:            return findPoint(ary, mid+1, end)        else: #            if ary[mid]
   

转载地址：http://zgnlf.baihongyu.com/