1. 题目描述
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
You are given a target value to search. If found in the array return its index, otherwise return -1
.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
2. 解题
在Leetcode上看到这个很有意思的题,在旋转过的有序数组中用O(logN)的时间复杂度找一个数,下面我尝试用我的方法解这道题。
方法的本质就是分情况。可知一个旋转后的有序数组可以分为两个部分,大致如下图所示,相当于横坐标为数组索引,纵坐标为数组值,然后把每个点连成线
暂且把左半部分称为左臂,右半部分称为右臂。现在开始分情况,可知任意一个旋转后的有序数组表示成上图的形式,有以下三种情况:
- 左臂比右臂长
- 右臂比左臂长
- 左臂右臂等长
那么现在仿照普通的二分查找,设左端点为left,右端点为right,然后取一个mid。可知对于上面第一种情况,mid一定落在左臂上。对于第二种情况,mid一定落在右臂上。对于第三种情况,由于C语言数组下标从0开始,所以mid也一定落在左臂上。
然后用代码判断mid是在左臂上还是右臂上,如果mid表示的值大于等于left表示的值,则mid在左臂上,否则mid在右臂上。
之后继续仿照二分查找,判断target在mid的左边还是右边。这时候分情况的作用就体现出来了。对于上面第一种情况,如果target >= arr[left] && target <= arr[mid]
则target在mid左边,所以收缩right,否则收缩left。对于第二种情况,如果target >= arr[mid] && target <= arr[right]
则target在mid右边,所以收缩left,否则收缩left。
然后重复上述步骤直到最终找到target。
3. 代码
int search(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) { // mid落在左臂
if (target >= nums[left] && target <= nums[mid]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
else if (nums[mid] < nums[left]) { // mid落在右臂
if (target >= nums[mid] && target <= nums[right]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return -1;
}