2、整数数组nums中的值互不相同,且循环有序。例如[4,5,6,7,0,1,2],设计一个时间复杂度为O(log n)的算法解决此问题。 示例1:输入:nums=[4,5,6,7,0,1,2], target =0。输出:4 示例2:输入: nums=[4.5,6,7,0,1,2],target=3。 输出:-1
时间: 2023-08-21 15:07:42 浏览: 56
这是一个经典的旋转排序数组问题,可以使用二分查找来解决。具体步骤如下:
1. 定义左右指针left和right,分别指向数组的起始和结束位置。
2. 当left <= right时,执行以下步骤:
a. 定义中间指针mid = (left + right) / 2。
b. 如果nums[mid] == target,则返回mid。
c. 如果nums[mid] >= nums[left],说明左半边是有序的。此时,如果target在左半边,则将right指针移动到mid - 1,否则将left指针移动到mid + 1。
d. 如果nums[mid] <= nums[right],说明右半边是有序的。此时,如果target在右半边,则将left指针移动到mid + 1,否则将right指针移动到mid - 1。
3. 如果没有找到target,则返回-1。
代码如下:
```python
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
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
```
时间复杂度为O(log n)。