假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它在数组中的下标,否则返回 -1 。 已知的是,数组中不存在重复的元素。 你的算法时间复杂度必须是 O(logn) 级别。
时间: 2023-06-03 12:03:33 浏览: 105
Python算法题源代码-LeetCode(力扣)-搜索旋转排序数组
我理解您的问题是关于如何在旋转排序数组中查找给定的目标值,并且时间复杂度必须为 O(logn)。下面是一个解决方案:
1. 首先找到旋转点,即数组中的最小元素。可以采用二分查找来实现。假设数组为 nums,初始时左指针 left=0,右指针 right=n-1,其中 n 是数组长度。每次将中间位置 mid=(left+right)/2 的值与右端点 right 处的值进行比较。如果 nums[mid] > nums[right],则最小值在 mid 的右边,令 left=mid+1;否则最小值在 mid 的左边或者自己就是最小值,令 right=mid。循环结束后,left 指向的就是旋转点的位置。
2. 然后对旋转后的两个有序子数组分别进行二分查找。如果目标值比 nums[left] 大或者比 nums[right] 小,那么直接返回 -1。否则,根据目标值与 nums[left] 的大小关系判断要在左边的子数组还是右边的子数组中进行查找。具体地,如果 nums[0] <= target <= nums[left-1],那么在左边子数组中查找,否则在右边子数组中查找。
代码如下:
```
int search(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
int pivot = left; // 旋转点的位置
left = 0;
right = numsSize - 1;
while (left <= right) {
int mid = (left + right) / 2;
int realmid = (mid + pivot) % numsSize; // 真实中间位置
if (nums[realmid] == target) {
return realmid;
} else if (nums[realmid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
阅读全文