lower_bound

[Alex Vinokur]

=============================
Windows 2000
MinGW 2.0.0.-2
GNU gcc/g++ version 3.2
=============================

I have some question concerning the lower_bound algorithm.

========= C++ code : File t.cpp : BEGIN =========
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

int main ()
{
typedef vector<int>::iterator iterator;

int d1[] = {0, 1, 2, 1, 3, 4, 2, 2, 2, 6, 7};
int d2[] = {0, 1, 2, 1, 3, 2, 4, 2, 2, 6, 7};

const int test_value = 3;

vector<int> v1(d1, d1 + sizeof(d1)/sizeof(d1[0]));
vector<int> v2(d2, d2 + sizeof(d2)/sizeof(d2[0]));

iterator pos1 = lower_bound(v1.begin(), v1.end(), test_value);
iterator pos2 = lower_bound(v2.begin(), v2.end(), test_value);

cout << "pos1 = " << distance (v1.begin(), pos1)
<< ", value1 = " << *pos1 << endl;

cout << "pos2 = " << distance (v2.begin(), pos2)
<< ", value2 = " << *pos2 << endl;


return 0;
}
========= C++ code : File t.cpp : END ===========


========= Compilation & Run : BEGIN =========

$ g++ t.cpp

$ a

pos1 = 4, value1 = 3
pos2 = 9, value2 = 6

========= Compilation & Run : END ===========


The lower_bound algorithm returns an iterator i
in the range [first, last) such
that for any iterator j in the range [first, i)
the following corresponding conditions hold :
*j < test_value.


For vector v1 and test_value = 3 :
Returned range = [v1.begin(), v1.begin() + 4)
{0, 1, 2, 1};
It seems to be OK.


For vector v2 and test_value = 3
Returned range = [v2.begin(), v2.begin() + 9);
{0, 1, 2, 1, 3, 2, 4, 2, 2};
However the range contains two values (3 and 4)
which the *j < test_value condition is not true for.

What is wrong?

Thanks,
==========================================
Alex Vinokur
mailto:[email protected]
http://sourceforge.net/users/alexvn
http://www.simtel.net/search.php?action=search&authorName=Alex+Vinokur
==========================================

 

[ES Kim]

=============================
Windows 2000
MinGW 2.0.0.-2
GNU gcc/g++ version 3.2
=============================

I have some question concerning the lower_bound algorithm.

========= C++ code : File t.cpp : BEGIN =========
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

int main ()
{
typedef vector<int>::iterator iterator;

int d1[] = {0, 1, 2, 1, 3, 4, 2, 2, 2, 6, 7};
int d2[] = {0, 1, 2, 1, 3, 2, 4, 2, 2, 6, 7};

const int test_value = 3;

vector<int> v1(d1, d1 + sizeof(d1)/sizeof(d1[0]));
vector<int> v2(d2, d2 + sizeof(d2)/sizeof(d2[0]));

iterator pos1 = lower_bound(v1.begin(), v1.end(), test_value);
iterator pos2 = lower_bound(v2.begin(), v2.end(), test_value);

cout << "pos1 = " << distance (v1.begin(), pos1)
<< ", value1 = " << *pos1 << endl;

cout << "pos2 = " << distance (v2.begin(), pos2)
<< ", value2 = " << *pos2 << endl;


return 0;
}
========= C++ code : File t.cpp : END ===========


========= Compilation & Run : BEGIN =========

$ g++ t.cpp

$ a

pos1 = 4, value1 = 3
pos2 = 9, value2 = 6

========= Compilation & Run : END ===========


The lower_bound algorithm returns an iterator i
in the range [first, last) such
that for any iterator j in the range [first, i)
the following corresponding conditions hold :
*j < test_value.


For vector v1 and test_value = 3 :
Returned range = [v1.begin(), v1.begin() + 4)
{0, 1, 2, 1};
It seems to be OK.


For vector v2 and test_value = 3
Returned range = [v2.begin(), v2.begin() + 9);
{0, 1, 2, 1, 3, 2, 4, 2, 2};
However the range contains two values (3 and 4)
which the *j < test_value condition is not true for.

What is wrong?

Thanks,
==========================================
Alex Vinokur
mailto:[email protected]
http://sourceforge.net/users/alexvn
http://www.simtel.net/search.php?action=search&authorName=Alex+Vinokur
==========================================

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

 

[Alex Vinokur]

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?

=====================================
Alex Vinokur
mailto:[email protected]
http://mathforum.org/library/view/10978.html
=====================================

 

[ES Kim]

[snip]

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?

None that I know of, but you can write your own function easily.

 

[Sam Holden]

[snip]

lower_bound() assumes a sequence is sorted.
Sort the vectors before you call lower_bound().

[snip]

Thanks.

Is there any function/method which detects if a vector is sorted?

None that I know of, but you can write your own function easily.

Or you could use existing STL features:

if(std::adjacent_find(v.begin(),v.end(),std::greater<value_type>())==v.end()){
//v is sorted
}