searchRange.cpp

#include <vector>

using namespace std;

class Solution
{
    // 何为二分查找，一次直接切一半，在中间位置往左或往右找。
    // 而不是类似双指针，遍历整个数组
public:
    int FindFirst(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int result = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            // 往左移，findLast是往右移，这是重大区别
            if (nums[mid] <= target)
            {
                if (nums[mid] == target)
                {
                    // 记录侯选位置而不是直接返回
                    result = mid;
                    // 继续向左看看还有没有更小的
                    right = mid - 1;
                }
                // 那么就往右看看
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                right = mid - 1;
            }
        }

        return result;
    }
    int FindLast(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int result = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target)
            {
                left = mid + 1;
                if (nums[mid] == target)
                {
                    result = mid;
                }
            }
            else
            {
                right = mid - 1;
            }
        }

        return result;
    }
    vector<int> searchRange(vector<int> &nums, int target)
    {
        // 首先查找第一个target，通过定义两个函数的形式，更清晰
        // 第一个函数，查找左边的那个target的位置
        int start = FindFirst(nums, target);
        int end = FindLast(nums, target);

        return {start, end};
    }
};