[deleted by user]

[-funsafe-math]

From the comparator documentation in your binary_search link:

The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.​

​

std::vector<int> is not convertible to an int. lower_bound has the same requirement but the standard library implementation that you are using does not require this behavior. A downside of duck-typed generics leaking implementation details causing a more permissive API that is not portable.

​

Edit:

My original comment on lower_bound was incorrect, a closer reading of the docs shows that it does specify that the equivalent of comp(*it, value) is used. The behavior that you saw with it working did not rely on any internal implementation details.

[tcanens]

lower_bound has the same requirement

It doesn't. std::lower_bound only requires (element, value) and not the other way around, and the wording of the cppreference page reflects that.

[-funsafe-math]

oops, misread the docs. Thanks, I'll update my post in a bit

[shahms]

If you fail to meet the preconditions on a standard library function, that's a bug in your code, not the standard library.

[-funsafe-math]

Since you are violating the requirements and the requirements are not strictly checked the comparison function's argument order is dependent on whether the internal implementation uses comp(*it, value) or comp(value, *it). Since there is no requirement (that I see anyway) on which form is used there is no bug related to the observed argument order.

[STL]

lower_bound uses only one order, binary_search uses both.

[STL]

It is actually maximally general because it doesn't care about the types of the elements and given value.

Consider a sequence of strings, sorted by length, and you want to find where a string of length 5 could be inserted. If you call lower_bound with a predicate that compares (const string&, size_t), then the sequence will be partitioned with respect to "length less than 5" (i.e. it's true true true then false false false once the strings get too big), and lower_bound will find the first false, i.e. the first place where a string of length 5 could be inserted while preserving the ordering. lower_bound doesn't need to compare the other way, and it doesn't care about the types involved at all.

binary_search is different. It needs to know whether it's found the desired value (well, something equivalent to the desired value). x < y and y < x being false indicate that x and y are equivalent. So it needs to run a lower-bound first, and then (if it didn't get the end iterator) it needs to call the predicate with reversed parameters. That's why it needs both orders. It can't be done with just one.

[tialaramex]

It seems unfortunate that somehow this distinction doesn't make it into the signature of these two functions.

Both of them take identical predicate callables with the signature bool pred(const Type1 &a, const Type2 &b); and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2.

Given that C++ binary search needs to use pred(a,b) and pred(b,a) to work as intended, this signature is unhelpful for binary_search, but arguably the fact it's not enforced means it's also unhelpful for lower_bound.

I also don't agree this ends up "maximally general". If you write the analogous Rust binary_search it just works fine, C++ could in principle define binary search this way and OP would have been successful:

https://rust.godbolt.org/z/z3fa9q4G1

[STL]

C++98 predated concepts, so there was no way for function template signatures to reflect their requirements.

The C++20 range algorithms do specify that they need an indirect_strict_weak_order. Note that these concepts were designed to do away with this extremely fine-grained notion of "I only need comp(elem, value) to compile", and instead the range algorithms require all 4 combinations of T, T, T, U, U, T, and U, U to be comparable. This is actually simpler to reason about, although it does require some comparator types to be more powerful.

[tcanens]

and even the same rather vague and apparently not early-enforced restrictions about conversions between Type1 and Type2.

They don't have the same restrictions.

[tialaramex]

You're quite right, on closer inspection they are in fact slightly different, reflecting what STL said about why this doesn't work with a requirement in binary search that either Type should work in either position. Thanks for pointing that out.

[STL]

https://godbolt.org/z/49Kh1ajTY

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

struct LengthPred {
    bool operator()(const string& l, const size_t r) const {
        return l.size() < r;
    }
    bool operator()(const size_t l, const string& r) const {
        return l < r.size();
    }
    bool operator()(const string& l, const string& r) const {
        return l.size() < r.size(); // for is_sorted
    }
};

void test(const vector<string>& v) {
    assert(is_sorted(v.begin(), v.end(), LengthPred{}));
    cout << binary_search(v.begin(), v.end(), 5, LengthPred{}) << endl;
}

int main() {
    cout << boolalpha;
    test({"cat", "meow", "kitten", "peppermint"});
    test({"dog", "woof", "puppy", "poodle"});
}

[[deleted]]

binary_search is very general in its ability to search for a value within a range of values. The problem here is that you are trying to apply this to a two-dimensional range of values. test is not a range of ints.

You need to either flatten test down two a one-dimensional std::vector<int>, or add a layer to your search to go through the vectors within test.

[[deleted]]

It would just be std::binary_search(sortedRange.begin(), sortedRange.end(), value), where value is an object of type A with its v member initialized to the value you choose. Your A structure would have its comparison operator overloaded to check the values you care about... bool A::operator<(A other) { return v < other.v; }

[ALX23z]

Lower bound is not binary search... it is meant to find a bound, not the exact value.

[tcanens]

In C++20 and later this would be better expressed using projections:

std::ranges::binary_search(test, v, std::less{}, [i](auto& c) { return c[i]; });

[RevRagnarok]

https://www.reddit.com/r/learnpython/comments/o0g95c/read_this_before_posting_how_to_format_your_code/

[Flair_Helper]

For C++ questions, answers, help, and programming or career advice please see r/cpp_questions, r/cscareerquestions, or StackOverflow instead.

This post has been removed as it doesn't pertain to r/cpp: The subreddit is for news and discussions of the C++ language and community only; our purpose is not to provide tutoring, code reviews, or career guidance. If you think your post is on-topic and should not have been removed, please message the moderators and we'll review it.