面试题 10.03. 搜索旋转数组

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:

输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出：-1 （没有找到）

提示:

• arr 长度范围在[1, 1000000]之间

Python 解答：
1.先找到分割点再二分查找

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        def findtarget(arr, l, r, target):
            if l < r:
                mid = (l+r) // 2
                if arr[mid] < target:
                    return findtarget(arr, mid+1, r, target)
                elif arr[mid] > target:
                    return findtarget(arr, l, mid-1, target)
                else:
                    return findtarget(arr, l, mid, target)
            if arr[l] == target: return l 
            else: return -1
        def findlowest(arr, l, r, target):
            if l < r:
                mid = (l+r) // 2
                if arr[mid] < arr[r]:
                    return findlowest(arr, l, mid, target)
                elif arr[mid] > arr[r]:
                    return findlowest(arr, mid+1, r, target)
                else:
                    return findlowest(arr, l, r-1, target)
            return r

        low = findlowest(arr, 0, len(arr)-1, target)
        if arr[low] == arr[-1]:
            k = len(arr)-1
            while arr[k] == arr[low]:
                k -= 1
            else:
                low = k+1

        if target == arr[0]:
            return 0
        elif target <= arr[-1]:
            return findtarget(arr, low, len(arr)-1, target)
        elif target > arr[-1]:
            return findtarget(arr, 0, low-1, target)