【python】：搜索旋转数组

搜索旋转数组。给定一个排序后的数组，包含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 （没有找到）

旋转数组即将数组全部向左或者向右移，类似一个循环。 例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。 一、二分法 left > mid:数组左半边先从left递增再骤降到某一数再递增到mid，数组右半边都大于等于mid； left < mid:数组左半边从left递增到mid； left = mid:数组左半边可能都是left或者是从中间某一个数开始递增到mid。

class Solution: def search(self, arr: List[int], target: int) -> int: if not arr: return -1 left = 0 right = len(arr)-1 while left < right : mid = (left + right)>>1 if arr[left]< arr[mid]: if arr[left]<=target and target<=arr[mid]: right = mid else: left = mid + 1 elif arr[left] > arr[mid]: if arr[left] <= target or target <= arr[mid]: right = mid else: left = mid + 1 elif arr[left] == arr[mid]: if arr[left] != target: left += 1 else: right = left return left if arr[left] == target else -1