难度: Medium
搜索旋转数组。给定一个排序后的数组，包含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 （没有找到）
提示:
运行时间: 23 ms
内存: 17.0 MB
class Solution:
def search(self, arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
if arr[left] == target:
return left
mid = (left + right) // 2
if arr[mid] == target:
right = mid
continue
if arr[left] == arr[right]:
left += 1
continue
if arr[mid] <= arr[right]:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
else:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
return -1
这道题涉及到在一个部分旋转的有序数组中寻找一个特定的元素。解题关键在于如何有效利用数组的部分有序特性来减少搜索范围。首先，通过比较数组首尾元素实现区间的切分。算法首先检查当前左边界元素是否是目标元素，如果是则直接返回。接着，计算中间索引，并检查中间元素是否为目标，如果是则更新右边界为中间，以缩小搜索范围并可能找到最小索引。然后，算法检查左半部分是否有序（即左端元素小于等于右端元素）。根据有序部分的情况，决定是向左还是向右继续搜索，从而不断缩小查找范围。通过这种方式，算法能够在对数时间内找到目标元素或确定其不存在。
时间复杂度: O(log n) in best case, O(n) in worst case
空间复杂度: O(1)
class Solution:
def search(self, arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
if arr[left] == target: # 直接检查左端是否是目标
return left
mid = (left + right) // 2
if arr[mid] == target: # 检查中间元素是否是目标
right = mid # 更新右边界以可能找到更小的索引
continue
if arr[left] == arr[right]: # 处理边界相等的情况
left += 1
continue
# 确定哪一半是有序的
if arr[mid] <= arr[right]: # 右半部有序
if arr[mid] < target <= arr[right]:
left = mid + 1 # 目标在右半部
else:
right = mid - 1 # 目标不在右半部
else: # 左半部有序
if arr[left] <= target < arr[mid]:
right = mid - 1 # 目标在左半部
else:
left = mid + 1 # 目标不在左半部
return -1 # 未找到目标
在此算法中，一旦发现`arr[left] == target`，就可以直接返回`left`，因为算法每次循环都会从左边界开始检查，且左边界逐步右移。因此，当遇到`arr[left] == target`时，即意味着在当前搜索范围内，`left`已经是目标值的最小可能索引。继续搜索将不会找到一个更小的索引，因为左边界的更新已经排除了所有之前的元素。
当`arr[left] == arr[right]`时，意味着无法确定目标值位于左侧还是右侧，因为两端的值相同时，中间的值也可能相同，从而使得无法判断哪一部分是有序的。通过递增`left`索引，算法试图去掉一个潜在的重复元素，以希望破坏重复性，找到非重复区间以继续二分查找。潜在的风险是，如果目标值恰好在这些被逐步排除的重复元素中的位置，这种方式可能会错过目标值。
将右边界更新为`mid`是为了尝试在数组中找到目标值的最小索引。这种方法基于二分查找逻辑减少搜索范围，同时保持目标值在新的搜索范围内。这种做法确实有助于逐步缩小范围到最左端的目标值。然而，仅当循环每次都检查`left`端的值，并且左端索引在每次循环中都适当更新时，这种方法才保证找到最小索引。如果存在其他路径可能错过最左端的目标值（如不恰当的跳过某些检查），则这种保证不再成立。