一、题目描述
整数数组 nums 按升序排列，数组中的值 互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k 上进行了 旋转，使数组变为：
[nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]
例如：
原数组: [0,1,2,4,5,6,7]
旋转后: [4,5,6,7,0,1,2]
给定旋转后的数组 nums 和目标值 target，如果 target 存在于数组中，返回它的下标，否则返回 -1。
要求时间复杂度：
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
示例 3
输入：nums = [1], target = 0
输出：-1
三、解题思路
这道题是 二分查找的经典变形题。
虽然数组被旋转了，但有一个重要性质：
每次二分时，一定有一半是有序的。
例如：
[4,5,6,7,0,1,2]
如果 mid = 6
4 5 6 | 7 | 0 1 2
left mid right
可以发现：
左半部分是有序的
因此我们可以通过判断 哪一部分有序 来缩小查找范围。
四、具体算法步骤
在二分查找过程中：
1 判断中点
mid = (left + right) / 2
如果
nums[mid] == target
直接返回 mid。
2 判断哪一半是有序的
情况1：左半部分有序
如果
nums[left] <= nums[mid]
说明区间
[left, mid]
是升序的。
这时判断 target 是否在该区间：
nums[left] <= target < nums[mid]
如果在：
right = mid – 1
否则：
left = mid + 1
情况2：右半部分有序
否则说明
[mid, right]
是升序的。
判断：
nums[mid] < target <= nums[right]
如果成立：
left = mid + 1
否则：
right = mid – 1
五、C语言代码实现
int search(int* nums, int numsSize, int target) {
int left = 0;
int right = numsSize – 1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (nums[mid] == target)
return mid;
// 左半部分有序
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid – 1;
else
left = mid + 1;
}
// 右半部分有序
else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid – 1;
}
}
return -1;
}
六、复杂度分析
时间复杂度
O(log n)
每次二分都会缩小一半搜索区间。
空间复杂度
O(1)
只使用了常数级变量。
七、总结
本题的核心思想是：
旋转数组在任意时刻必然有一半是有序的。
利用这一特点，可以在二分查找时快速判断 target 应该落在哪一部分，从而保持 O(log n) 的时间复杂度。
