446,233 Members | 1,806 Online
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,233 IT Pros & Developers. It's quick & easy.

# lower_bound

 P: n/a ============================= 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 #include #include #include using namespace std; int main () { typedef vector::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 v1(d1, d1 + sizeof(d1)/sizeof(d1[0])); vector 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:al****@connect.to http://sourceforge.net/users/alexvn http://www.simtel.net/search.php?act...e=Alex+Vinokur ========================================== Jul 19 '05 #1
4 Replies

 P: n/a "Alex Vinokur" wrote in message news:bg************@ID-79865.news.uni-berlin.de... ============================= 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 #include #include #include using namespace std; int main () { typedef vector::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 v1(d1, d1 + sizeof(d1)/sizeof(d1[0])); vector 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:al****@connect.to http://sourceforge.net/users/alexvn http://www.simtel.net/search.php?act...e=Alex+Vinokur ========================================== lower_bound() assumes a sequence is sorted. Sort the vectors before you call lower_bound(). -- ES Kim Jul 19 '05 #2

 P: n/a "ES Kim" wrote in message news:bg**********@news1.kornet.net... [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? ===================================== Alex Vinokur mailto:al****@connect.to http://mathforum.org/library/view/10978.html ===================================== Jul 19 '05 #3

 P: n/a "Alex Vinokur" wrote in message news:bg************@ID-79865.news.uni-berlin.de... "ES Kim" wrote in message news:bg**********@news1.kornet.net... [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. -- ES Kim Jul 19 '05 #4

 P: n/a On Thu, 31 Jul 2003 12:35:31 +0900, ES Kim wrote: "Alex Vinokur" wrote in message news:bg************@ID-79865.news.uni-berlin.de... "ES Kim" wrote in message news:bg**********@news1.kornet.net... [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::great er())==v.end()){ //v is sorted } -- Sam Holden Jul 19 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion.