solution.md

# 搜索旋转排序数组
<p>整数数组 <code>nums</code> 按升序排列，数组中的值 <strong>互不相同</strong> 。</p>
<p>在传递给函数之前，<code>nums</code> 在预先未知的某个下标 <code>k</code>（<code>0 <= k < nums.length</code>）上进行了 <strong>旋转</strong>，使数组变为
    <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code>（下标 <strong>从 0 开始</strong>
    计数）。例如， <code>[0,1,2,4,5,6,7]</code> 在下标 <code>3</code> 处经旋转后可能变为 <code>[4,5,6,7,0,1,2]</code> 。
</p>
<p>给你 <strong>旋转后</strong> 的数组 <code>nums</code> 和一个整数 <code>target</code> ，如果 <code>nums</code> 中存在这个目标值
    <code>target</code> ，则返回它的下标，否则返回 <code>-1</code> 。
</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 0<strong><br />输出：</strong>4</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 3<strong><br />输出：</strong>-1</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>nums = [1], target = 0<strong><br />输出：</strong>-1</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>1 <= nums.length <= 5000</code></li>
    <li><code>-10^4 <= nums[i] <= 10^4</code></li>
    <li><code>nums</code> 中的每个值都 <strong>独一无二</strong></li>
    <li>题目数据保证 <code>nums</code> 在预先未知的某个下标上进行了旋转</li>
    <li><code>-10^4 <= target <= 10^4</code></li>
</ul>
<p> </p>
<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(log n)</code> 的解决方案吗？</p>
<p><p>整数数组 <code>nums</code> 按升序排列，数组中的值 <strong>互不相同</strong> 。</p>
<p>在传递给函数之前，<code>nums</code> 在预先未知的某个下标 <code>k</code>（<code>0 <= k < nums.length</code>）上进行了 <strong>旋转</strong>，使数组变为
    <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code>（下标 <strong>从 0 开始</strong>
    计数）。例如， <code>[0,1,2,4,5,6,7]</code> 在下标 <code>3</code> 处经旋转后可能变为 <code>[4,5,6,7,0,1,2]</code> 。
</p>
<p>给你 <strong>旋转后</strong> 的数组 <code>nums</code> 和一个整数 <code>target</code> ，如果 <code>nums</code> 中存在这个目标值
    <code>target</code> ，则返回它的下标，否则返回 <code>-1</code> 。
</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 0<strong><br />输出：</strong>4</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>nums = [4,5,6,7,0,1,2], target = 3<strong><br />输出：</strong>-1</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>nums = [1], target = 0<strong><br />输出：</strong>-1</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>1 <= nums.length <= 5000</code></li>
    <li><code>-10^4 <= nums[i] <= 10^4</code></li>
    <li><code>nums</code> 中的每个值都 <strong>独一无二</strong></li>
    <li>题目数据保证 <code>nums</code> 在预先未知的某个下标上进行了旋转</li>
    <li><code>-10^4 <= target <= 10^4</code></li>
</ul>
<p> </p>
<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(log n)</code> 的解决方案吗？</p>
<p>以下错误的选项是？</p></p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    int res;
    vector<int> 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<int> &nums, int target)
    {
        return bs(nums, 0, nums.size(), target);
    }
    int bs(vector<int> &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<int> &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<int> &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<int> &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;
    }
};
```