solution.md

# 在排序数组中查找元素的第一个和最后一个位置

<p>给定一个按照升序排列的整数数组 <code>nums</code>，和一个目标值 <code>target</code>。找出给定目标值在数组中的开始位置和结束位置。</p>
<p>如果数组中不存在目标值 <code>target</code>，返回 <code>[-1, -1]</code>。</p>
<p><strong>进阶：</strong></p>
<ul>
    <li>你可以设计并实现时间复杂度为 <code>O(log n)</code> 的算法解决此问题吗？</li>
</ul>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>nums = [5,7,7,8,8,10], target = 8<strong><br />输出：</strong>[3,4]</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>nums = [5,7,7,8,8,10], target = 6<strong><br />输出：</strong>[-1,-1]</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>nums = [], target = 0<strong><br />输出：</strong>[-1,-1]</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>0 <= nums.length <= 10<sup>5</sup></code></li>
    <li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
    <li><code>nums</code> 是一个非递减数组</li>
    <li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li>
</ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp
int main()
{
    Solution sol;
    vector<int> res;
    vector<int> nums{5, 7, 7, 8, 8, 10};
    int target = 8;

    res = sol.searchRange(nums, target);

    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int left(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                if (mid == 0 || nums[mid - 1] < target)
                {
                    return mid;
                }
                right = mid + 1;
            }
            else if (nums[mid] > target)
            {
                right = mid + 1;
            }
            else
            {
                left = mid - 1;
            }
        }
        return -1;
    }
    int right(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                if (mid == nums.size() - 1 || nums[mid + 1] > target)
                {
                    return mid;
                }
                left = mid - 1;
            }
            else if (nums[mid] > target)
            {
                right = mid + 1;
            }
            else
            {
                left = mid - 1;
            }
        }
        return -1;
    }

    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> result;
        result.push_back(left(nums, target));
        result.push_back(right(nums, target));
        return result;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> res(2, -1);
        int i = 0, j = nums.size();
        int mid = (i + j) / 2;

        int p = -1;
        while (i < j)
        {
            if (nums[mid] == target)
            {
                p = mid;
                break;
            }
            if (nums[mid] > target)
            {
                if (j == mid)
                    break;
                j = mid;
                mid = (i + j) / 2;
            }
            else
            {
                if (i == mid)
                    break;
                i = mid;
                mid = (i + j) / 2;
            }
        }

        if (p == -1)
        {
            return res;
        }
        else
        {
            int a = p, b = p;
            while (a > 0 && nums[a - 1] == target)
                a--;
            while (b < nums.size() - 1 && nums[b + 1] == target)
                b++;
            vector<int> h;
            h.push_back(a);
            h.push_back(b);
            return h;
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> res;
        res.push_back(binary_search_begin(nums, target));
        res.push_back(binary_search_end(nums, target));
        return res;
    }

private:
    int binary_search_begin(vector<int> nums, int target)
    {
        int lo = -1;
        int hi = nums.size();
        while (lo + 1 < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (target > nums[mid])
            {
                lo = mid;
            }
            else
            {
                hi = mid;
            }
        }
        if (hi == nums.size() || nums[hi] != target)
        {
            return -1;
        }
        else
        {
            return hi;
        }
    }
    int binary_search_end(vector<int> nums, int target)
    {
        int lo = -1;
        int hi = nums.size();
        while (lo + 1 < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
            {
                hi = mid;
            }
            else
            {
                lo = mid;
            }
        }
        if (lo == -1 || nums[lo] != target)
        {
            return -1;
        }
        else
        {
            return lo;
        }
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        int start = -1, end = -1;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == target)
            {
                if (start == -1)
                    start = i;
                end = i;
            }
        }
        vector<int> ans;
        ans.push_back(start);
        ans.push_back(end);
        return ans;
    };
};
```