Hi,

I was looking through code of MS implementation of STL's binary_search and found a part of code whose purpose I can't explain, and I would appreciate any help.

Here's the code:
"lower_bound() returns an iterator addressing the first position within the sorted sequence marked off by [first,last) into which value may be inserted without violating the sorted ordering of the container. This position will mark off a value either greater than or equal to value." [C++ Primer 3rd ed.].

In other words, upon return from lower_bound(), _First will point to an element that is either greater or equal to the sought item (= "_Val is less or equal than _First"). So, if _Val < *First, the the sought item is not present in the range. As I see it, "return !(_Val < *_First)" would be enough. Why do they have much more than that in the last statement?

Thanks

Hi rom. That is a hell of a question!



The way I see it this will only return true if the _First is not pointing to _Last AND _Val is equal to *_First.

Using this list for an example:
1
10
20
30

If you have a value that is 15, it will return 0.

_First != _Last - True (_First should point to 20)
_Val < *_First - True - thereby negating to false

So TRUE && FALSE is FALSE.

If you have a value that is 30, it will also return false.

_First != _Last - False (Already false)

In fact this will only return true for values of 1, 10 & 20 unless I am missing something...

I don't know if this does you any good, but as I am not really familiar with the binary_search function, I am not sure what it is supposed to return.

Thank you. You are most likely correct. My misunderstanding stemmed from forgetting that != has higher precedence than &&, and your reply reminded me of that. I understand now.

BTW, here's what binary_search() does: "binary_search() looks for value within the sorted sequence marked off by [first,last). If the value is found, true is returned, otherwise false is returned."

Hence the reason I suggest you always use parens scattered throughout code. Putting more than necessary doesn't hurt, putting fewer sometimes aids in ambiguity.
Yes, I know it's M$ code, not yours, but it illustrates my point.

I agree with you regarding the use of parentheses and tend to use them liberally.

What makes me feel even more ashamed is that I just realized that the mistake I made was even worse: due to not having programmed in C/C++ for a relatively long period of time or being just tired, I mistook != as a compound assignment operator ("negate and then assign"). What a foolish thing to do that was!

That is what I was afraid of. Something doesn't seem right with my logic then in my first post. I put that it won't return true if the last value is found. Where have I gone wrong?

It also makes you wonder why they don't just put:

I don't doubt that there is a reason, but my simpleton mind can't grasp it...

I think you were right in your first post because notation [a, b) means from a to b but not including b (sometimes called a left-inclusive interval). [a, b] would be an inclusive range (or interval). Perhaps, a sample code would be of value (it's from the same book):

Right. Thanks, I totally missed that. That does make sense then in what it is doing and why it is using the return statement that it does.

However, I am still confused of why you would want to use this. In your example above, if I pass the number 51 it will return false, but 51 is in the list. Why would I want that to be false if I simply want to know if the number 51 is in the list?

Once again, I am sure there is a reason, but I am not seeing it.

Why do you think the function will return false if you pass it 51? Are you misinterpreting the range, by any chance? The range you specify by first and last sets lower and upper bounderies in the container for the search (similar to start and end position usually passed to string searching functions). It is not a range of values that the number you are seaking (51, here) falls into. For example, you could have a container (e.g. an array) with 100 items and want to find out if 15 is present in the first 27. So, you'd call binary_search(&ar[0], &ar[27], 15). It would search from ar[0] to ar[26], inclusively.

Sorry, I didn't count the array elements. I just assumed that you wouldn't want to pass an out of bounds array element to the function like your sample does. There are only 12 elements in the array and it is passing the 13th element to tell it to search the whole list? Maybe its just me, but that makes me a little nervous. It's probably not something I will be using any time soon anyway...

Anyway, this has been a great discussion. I hope that you will stick around GIDForums as your insight and point of view would be a very welcome addition.