二分查找查找是在有序列表中查找指定值的有效数算，思想很简单，但是细节和变化很多。
这里主要记录最近学习到的模板，参考知乎问题回答。

找下界

也就是返回列表中大于等于目标值的第一个元素位置，因此返回情况有两种，指向为目标值，说明在列表中找到了目标值；指向不为目标值，说明没有找到。

int lower_bound(vector<int>& nums, int target, int first, int last){
        if (first < 0 || last < 0) return  -1;
        int mid;
        int left = first;
        int right = last;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == last) return -1; // 没找到
        if (nums[left] != target) return -1; //不等于目标值，没找到
        return left;
    }

在STL中std::lower_bound实现了这一功能，原型是

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
(until C++20)
template< class ForwardIt, class T >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
(since C++20)
------------------------------------------------------------------------------------------------------
template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
(until C++20)
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
(since C++20)

返回一个指向迭代器区间[first, last)中第一个大于等于目标元素的迭代器，如果没有找到返回的是last。换言之可以验证返回迭代器指向元素是否为目标元素，如果是则是下界，如果不是，没有找到目标元素。

找上界

查找有序列表中，大于key的第一个元素位置，因此判断返回位置减1是够和目标值相同，可以判断有没有找到目标值。一种实现如下，只需在条件判断部分取否即可：

int upper_bound(vector<int>& nums, int target, int first, int last){
        if (first < 0 || last < 0) return  -1;
        int mid;
        int left = first;
        int right = last;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > target) right = mid;
            else left = mid + 1;
        }
        if (left == first) return -1; // 没找到
        if (nums[left - 1] != target) return -1; //不等于目标值，没找到
        return left;
    }

同样在STL中已经实现了这一功能。

ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
(until C++20)
template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
(since C++20)
------------------------------------------------------------------------------------------------------  
template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
(until C++20)
template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
(since C++20)

返回一个指向迭代器区间[first, last)中第一个大于目标元素的迭代器，如果没有找到返回的是last。换言之可以验证返回迭代器减1看是否找到目标元素。

找区间

只需结合上面的两个函数即可，返回[lower_bound(value), upper_bound(value))开区间内都是目标值，STL中可以用std::equal_range。

二分std::binary_search

template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

二分查找是否包含某个元素，返回bool。