二分法：查找区间search for a range

问题描述：

给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。

例如:

arr = [2,3,4,4,4],target = 4,最终结果为[2,4]

arr = [2,3,4,5,6],target = 4,最终结果为[2,2]

分析：

最终的结果为一个区间，区间的话肯定有左端点，右端点。

题目是给定了一个有序数组，那么我们的目标就是确认左端点和右端点分别是多少即可。左端点即左侧再有没有比左端点更小的数值了，右端点即右侧再也没有比右端点更大小数值了。

确认左端点的过程如下:

arr = [2,3,4,4,4],target = 4,那么需要走一遍二分查找的整个过程

如果我们发现arr[mid] == target,这个时候仍然需要进行判断，即mid == 0 或者arr[mid-1] < target，那么才能够认为此时 left = mid；即此时arr[mid]的左侧已经没有和target相等的节点了。

确认右端点的过程如下:

arr = [2,3,4,4,5],target = 4,那么同样需要走一遍二分查找的整个过程

如果我们发现arr[mid] == target,这个时候仍然需要进行判断，即mid == arr.size()-1 或者arr[mid+1] > target，那么才能够认为此时 right = mid；即此时arr[mid]的右侧已经没有和target相等的节点了。

以上过程实现如下:

pair<int,int> get_target_range(std::vector<int> &arr, int target) {
    int begin = 0;
    int end = arr.size() - 1;
    pair<int,int> range;
    range.first = -1;
    range.second = -1;
    /*计算左边界*/
    while(begin <= end) {
        int mid = (begin + end) / 2;
        if (arr[mid] == target) {
            if (mid == 0 || arr[mid - 1] < target) {//arr[mid]左侧没有比target更小的
                range.first = mid;
                break;
            } 
            end = mid - 1; //控制左侧的遍历
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }
    
    /*计算右边界*/
    begin = 0;
    end = arr.size() - 1;
    while(begin <= end) {
        int mid = (begin + end) / 2;
        if (arr[mid] == target) {
            /*arr[mid]右侧没有比target更大的*/
            if (mid == arr.size() - 1 || arr[mid + 1] > target) {
                range.second = mid;
                break;
            } 
            begin = mid + 1;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }

    return range;
}      

#include <iostream>
#include <vector>

using namespace std;
pair<int,int> get_target_range(std::vector<int> &arr, int target) {
    int begin = 0;
    int end = arr.size() - 1;
    pair<int,int> range;
    range.first = -1;
    range.second = -1;

    while(begin <= end) {
        int mid = (begin + end) / 2;
        if (arr[mid] == target) {
            if (mid == 0 || arr[mid - 1] < target) {
                range.first = mid;
                break;
            } 
            end = mid - 1;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }

    begin = 0;
    end = arr.size() - 1;
    while(begin <= end) {
        int mid = (begin + end) / 2;
        if (arr[mid] == target) {
            if (mid == arr.size() - 1 || arr[mid + 1] > target) {
                range.second = mid;
                break;
            } 
            begin = mid + 1;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }

    return range;
}

int main() {
    std::vector<int> arr1;
    int n;
    cin >> n;
    for (int i = 0;i < n; ++i) {
        int tmp;
        cin >> tmp;
        arr1.push_back(tmp);
    }
    int target;
    cin >> target;
    cout << "[" << get_target_range(arr1, target).first << "," << get_target_range(arr1, target).second << "]"; 
    return 0;
}      

#输入
5
2 3 4 4 4
#输入target
4
#输出
[2,4]

#输入
5
4 4 4 4 4
#输入target
4
#输出
[0,4]