template <class ForwardIterator, class T>

  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)

{

  first = std::lower_bound(first,last,val);

  return (first!=last && !(val<*first));

}

#include<cstdio>

#include<iostream>

#include<string>

#include<algorithm>

#include<iterator>

#include<sstream>//istringstream

#include<cstring>

using namespace std;

//return first element >=

int * lowerbound(int *first, int* last, int value)

{

    int* it;

    int count=last-first;

    int step;

    while(count>0)

    {

        it=first;

        step=count/2;

        it+=step;

        //it指向的<, ++后排除<

        if(*it<value)

        {

            first=++it;

            count-=step+1;

        }

        else//左边

            count=step;

    }

    return first;

}

//return first element >

int* upperbound(int *first, int *last, int value)

{

    int count=last-first;

    int step;

    int *it;

    while(count>0)

    {

        step=count/2;

        it=first+step;

        //it指向 <= ,++后排除<=

        if(!(value<*it))

        {

            first=++it;

            count-=step+1;

        }

        else

        {

            count=step;

        }

    }

    return first;

}

int main()

{

    int a[]={ 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

    int *lb=lowerbound(a, a+sizeof(a)/sizeof(int), 4);

    cout<<*lb<<endl;

    int *ub=upperbound(a, a+sizeof(a)/sizeof(int), 4);

    cout<<*ub<<endl;

    return 0;

}