第5章、STL之二分查找

STL强化之二分查找

Leetcode题目传送门

场景：对付就业笔试+比赛+项目（精简代码，不影响效率）
在比赛等场景，需要大幅度的精简代码，希望借助STL，一些常用的算法就不自己实现了。
备注：在面试的场景，得会手撕。

一、STL中二分查找相关的函数

下面的算法内部都是二分查找实现的，所以时间复杂度是 $O(logn)$
完全可以代替我们手写的二分查找。

1）lower_bound（最重要）

返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置.重载函数使用自定义比较操作

template<class FwdIt, class T> 
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);
//Output：可以插入（如果没有的话）/找的值（无论有没有重复）所在位置，的正向迭代器。
//Input：输入参数是，正向迭代器起始，正向迭代器结束，要查找的值


template<class FwdIt, class T, class Pred> 
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);
//Output：可以插入（如果没有的话）/找的值（无论有没有重复）所在位置，的正向迭代器。
//Input：输入参数是，正向迭代器起始，正向迭代器结束，要查找的值，自定义比较操作

2）upper_bound

返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值.重载函数使用自定义比较操作

template<class FwdIt, class T> 
FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);

template<class FwdIt, class T, class Pred> 
FwdIt upper_bound(FwdIt first, FwdIt last, const T& val, Pred pr);

3）equal_range

功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound

template<class FwdIt, class T> 
pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last,const T& val);

template<class FwdIt, class T, class Pred> 
pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last,const T& val, Pred pr);

代码测试


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


int main () 
{
    int myints[] = {1,2,2,3,3,3,5,5};
    vector<int> v(myints,myints+8); 

    //用这个接收 
    pair<vector<int>::iterator,vector<int>::iterator> bounds;


      bounds=equal_range (v.begin(), v.end(), 3); 

    cout << "lower_bound " << (bounds.first - v.begin())<<endl;
    cout << "upper_bound " << (bounds.second - v.begin()) <<endl;



      return 0;
}

输出

lower_bound 3
upper_bound 6

4）binary_search

在有序序列中查找value,找到返回true.重载的版本使用指定的比较函数对象或函数指针来判断相等

template<class FwdIt, class T> 
bool binary_search(FwdIt first, FwdIt last, const T& val);
//Output：查找某个元素是否出现，返回bool
//Input：输入参数是，正向迭代器起始，正向迭代器结束，要查找的值

template<class FwdIt, class T, class Pred> 
bool binary_search(FwdIt first, FwdIt last, const T& val,Pred pr);
//Output：查找某个元素是否出现，返回bool
//Input：输入参数是，正向迭代器起始，正向迭代器结束，要查找的值，自行定义的规则

二、题解

1）还不够灵活的使用函数

class Solution {
public:
    int search(vector<int>& nums, int target) {

        bool rt=binary_search(nums.begin(),nums.end(),target);
        if(false==rt)
        {
            return -1;
        }
        else
        {
            vector<int>::iterator it=lower_bound(nums.begin(),nums.end(),target);

            return it-nums.begin();

        }



    }
};

2）更加灵活的使用函数

    class Solution {
    public:
        int search(vector<int>& nums, int target) {


            vector<int>::iterator it=lower_bound(nums.begin(),nums.end(),target);

            int num=it-nums.begin();
            if(nums.size()==num)
            {
                //最末尾了
                return -1;
            }
            else if(target==(*it))
            {
                return num;
            }
            else
            {
                //虽然是0，但是不等
                return -1;
            }

        }
    };