Python 实现旋转数组中的目标值搜索 (二分查找)

问题描述：

给定一个整数数组 nums，它按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。

给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路：

使用二分查找的思路寻找目标值，需要注意的是，由于数组经过旋转，无法直接使用二分查找。因此，我们需要在二分查找的过程中，判断数组的左半部分和右半部分哪一部分是有序的，然后再根据有序的那一部分判断目标值是否在这一部分中，从而确定下一步查找的区间。

具体步骤如下：

定义左右指针 left 和 right，分别指向数组的左右端点。
进行二分查找，计算中间位置 mid。
判断 mid 对应的值是否等于目标值 target，若是则返回 mid。
判断左半部分是否有序，如果有序并且目标值在左半部分，则将右指针 right 移动到 mid-1，否则将左指针 left 移动到 mid+1。
判断右半部分是否有序，如果有序并且目标值在右半部分，则将左指针 left 移动到 mid+1，否则将右指针 right 移动到 mid-1。
重复步骤 2~5，直到找到目标值或者左指针大于右指针时退出循环。

时间复杂度： O(log n)

代码实现：

def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # 判断左半部分是否有序
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 否则右半部分有序
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

示例：

nums = [4,5,6,7,0,1,2]
target = 0
index = search(nums, target)
print(index)  # 输出：4