#include<iostream>
#include<vector>
using namespace std;

// 二分查找target
int find_target(vector<int> &vec, int target){
    int low = 0, high = vec.size()-1, mid = 0;
    while(low <= high){
        mid = (low + high)/2;
        if (vec[mid] > target)
            high = mid - 1;
        else if (vec[mid] < target)
            low = mid + 1;
        else //find the target
            return mid;
    }
    //the array does not contain the target
    return -1;
}

// 二分查找target的上界
int find_target_upper_bound(vector<int> &vec, int target){
    int low = 0, high = vec.size()-1, mid = 0;
    //target is greater than every element in array
    if(target > vec[high]) return -1;
    while(low <= high){
        mid = (low + high)/2;
        if (vec[mid] > target)
            high = mid - 1;
        else if (vec[mid] < target)
            low = mid + 1;
        else //find the target
            return mid;
    }
    return mid+1; // upper bound
}

// 二分查找target的下界
int find_target_lower_bound(vector<int> &vec, int target){
    int low = 0, high = vec.size()-1, mid = 0;
    //target is less than every element in array
    if(target < vec[low]) return -1;
    while(low <= high){
        mid = (low + high)/2;
        if (vec[mid] > target)
            high = mid - 1;
        else if (vec[mid] < target)
            low = mid + 1;
        else //find the target
            return mid;
    }
    return mid; // lower bound
}

int main(){
    vector<int> arr = {2,3,5,6,7,8};
    for(auto v : arr) cout << v << " ";
    cout << endl;
    // find target
    for(auto v : arr)
            cout << find_target(arr, v) << " ";
    cout << find_target(arr, 4) << " " << find_target(arr, 9) << endl;
    // find upper bound
    for(auto v : arr)
            cout << find_target_upper_bound(arr, v) << " ";
    cout << find_target_upper_bound(arr, 4) << " " << find_target_upper_bound(arr, 9) << endl;
    // find lower bound
    for(auto v : arr)
        cout << find_target_lower_bound(arr, v) << " ";
    cout << find_target_lower_bound(arr, 4) << " " << find_target_lower_bound(arr, 1) << endl;
    return 0;
}