binary_sarch.cpp

template<class T>
bool isOK(vector<T> a, int index, T key) 
{
    // ここの比較でupper boundかlower bound か決まる
    if (a[index] > key) {
        return true;
    }
    else {
        return false;
    }
}

template<class T>
T binarysearch(vector<T> a, T key) 
{
    int left = -1;
    int right = (int) a.size();
    while (abs(right - left) > 1) {
        int mid = left + (right - left) / 2;
        /*
        cout << "left " << left << endl;
        cout << "right " << right << endl;
        cout << "mid " << mid << endl;
        */
        if (isOK(a, mid,key)) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    //cout << "return " << right << endl;
    return right;
}