Search

Just return the index

Binary Search [Left, Right)

int binarySearch(const vector<int>& Array, int key){
    int left=0;
    int right=Array.size();

    while(left != right){
        int mid = left + (right-left)/2;
        if(Array[mid]==key) return mid; // Found

        else if(Array[mid]<key) left=mid+1;  // key should be in right part
        else right=mid;         // key should be in left part
    }
    return -1; // Not found
}

Binary Search [Left, Right]

int binarySearch(const vector<int>& Array, int key){
    int left=0;
    int right=Array.size()-1;

    while(left <= right){
        int mid = left + (right-left)/2;
        if(Array[mid]==key) return mid; // Found

        else if(Array[mid]<key) left=mid+1;  // key should be in right part
        else right=mid-1;         // key should be in left part
    }
    return -1; // Not found
}

Lower bound: first element that is greater-or-equal.

Upper bound: first element that is strictly greater.

Lower bound [Left, Right)

std::lower_bound
default (1) 
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

int lowerBound(const vector<int>& Array, int key){
    int left=0;
    int right=Array.size();

    while(left != right){
        int mid = left + (right-left)/2;

        if(Array[mid]<key) left=mid+1;  // key should be in right part
        else right=mid;         // key should be in left part
    }
    return left; 
}

Upper bound [Left, Right)

std::upper_bound
default (1) 
template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

int upperBound(const vector<int>& Array, int key){
    int left=0;
    int right=Array.size();

    while(left != right){
        int mid = left + (right-left)/2;

        if(Array[mid]<=key) left=mid+1;  // key should be in right part
        else right=mid;         // key should be in left part
    }
    return left; 
}