# 搜索旋转排序数组
整数数组 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 。
示例 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
提示：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums 中的每个值都 独一无二- 题目数据保证
nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int res;
vector nums{4, 5, 6, 7, 0, 1, 2};
int target = 0;
res = sol.search(nums, target);
cout << res << " ";
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
int search(vector &nums, int target)
{
return bs(nums, 0, nums.size(), target);
}
int bs(vector &nums, int i, int j, int &target)
{
if (i > j)
return -1;
int k = (i + j) / 2;
if (nums[k] == target)
return k;
if (nums[k] < nums[j])
{
if (target < nums[k] || target > nums[j])
return bs(nums, i + 1, k - 1, target);
else
return bs(nums, k - 1, j, target);
}
else
{
if (target > nums[k] || target < nums[i])
return bs(nums, k + 1, j, target);
else
return bs(nums, i - 1, k, target);
}
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
int search(vector &nums, int target)
{
int lo = 0;
int hi = nums.size() - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[lo] <= nums[mid])
{
if (nums[lo] <= target && target < nums[mid])
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
else
{
if (nums[mid] < target && target <= nums[hi])
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
}
return -1;
}
};
```
### B
```cpp
class Solution
{
public:
int search(vector &nums, int target)
{
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
int newMid = nums[0] > nums[mid] ? nums[mid] + 0x3f3f3f3f : nums[mid];
int newTarget = nums[0] > target ? target + 0x3f3f3f3f : target;
if (newMid == newTarget)
return mid;
else if (newMid < newTarget)
l = mid + 1;
else if (newMid > newTarget)
r = mid - 1;
}
return -1;
}
};
```
### C
```cpp
class Solution
{
public:
int search(vector &nums, int target)
{
int n = nums.size();
if (n == 0)
return -1;
int loc = -1;
int i = 0;
int j = n - 1;
int cur = i;
while (i <= j)
{
if (nums[i] == target)
{
loc = i;
break;
}
else if (nums[j] == target)
{
loc = j;
break;
}
if ((nums[i] > target && nums[j] < target) || i == j)
{
break;
}
if (nums[i] < target)
{
int mid = (i + j) / 2;
if (i == mid || j == mid)
return loc;
while (nums[mid] < nums[i])
{
j = mid - 1;
mid = (i + j) / 2;
}
if (nums[mid] < target)
{
i = mid;
continue;
}
else
{
j = mid;
while (i <= j)
{
mid = (i + j) / 2;
if (nums[mid] == target)
{
loc = mid;
break;
}
if (nums[mid] > target)
j = mid - 1;
else
i = mid + 1;
}
}
}
if (nums[j] > target)
{
int mid = (i + j) / 2;
if (i == mid || j == mid)
return loc;
while (nums[mid] > nums[j])
{
i = mid + 1;
mid = (i + j) / 2;
}
if (nums[mid] > target)
{
j = mid;
continue;
}
else
{
i = mid;
while (i <= j)
{
mid = (i + j) / 2;
if (nums[mid] == target)
{
loc = mid;
break;
}
if (nums[mid] > target)
j = mid - 1;
else
i = mid + 1;
}
}
}
}
return loc;
}
};
```