> binary_search is defined as
>
> bool binary_search(ForwardIterator first, ForwardIterator last,
>             const T& value);
>
> or
>
> bool binary_search(ForwardIterator first, ForwardIterator last,
>             const T& value, Compare comp);
>
> (in the January 1996 draft).
>
> It is really unfortunate that the return value is bool.  This
> discards information, since in many cases it would be more
> useful to return an iterator to the found object, or return last
> if no object is found.  The reason is that Compare might only
> compare some fields of T, while information might be stored in
> the other fields.  Also, this would be more consistent with other
> STL algorithms that search: the "not found" condition is signaled
> by the return value equaling the end iterator.

There is a way around this.  Define a comparison functor that you pass in
as the 3rd arg to binary_search(), and store the required iterator in that.
 E.g.:

class MyComp {
 // declare iterator;
 bool operator () (const X& x, const X& y) const  { /* assign iterator when
found */ }
};

This could be templated.

However, I agree.  It makes more sense to return the past-the-end iterator
value if it's not found, and an iterator to the found object if it _is_
found (like Lisp's MEMBER predicate).

Roly Perera
----
Interactive Computers Ltd
3 Cumberland Road
Acton
London  W3 6EX
Phone: +44 (956) 414 395
Phax:  +44 (181) 932 2490
Email: rolyp@private.nethead.co.uk
----
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roly Perera wrote:
>
> binary_search is defined as
>
> bool binary_search(ForwardIterator first, ForwardIterator last,
>                  const T& value);
>
> or
>
> bool binary_search(ForwardIterator first, ForwardIterator last,
>                  const T& value, Compare comp);
>
> (in the January 1996 draft).
>
> It is really unfortunate that the return value is bool.  This
> discards information, since in many cases it would be more
> useful to return an iterator to the found object, or return last
> if no object is found.  The reason is that Compare might only
> compare some fields of T, while information might be stored in
> the other fields.  Also, this would be more consistent with other
> STL algorithms that search: the "not found" condition is signaled
> by the return value equaling the end iterator.

I agree that the binary_search algorithm is useless in its present form;
however, there are several variants which are useful and provide the
information that you are looking for.  Check out the descriptions for
the following algorithms:  lower_bound, upper_bound, and equal_range.

--
John I. Moore, Jr.      phone:  (301) 924-0680
SoftMoore Consulting    email:  70672.1744@compuserve.com
16233 Monty Court
Rockville, MD  20853-1344


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

binary_search is defined as

bool binary_search(ForwardIterator first, ForwardIterator last,
            const T& value);

or

bool binary_search(ForwardIterator first, ForwardIterator last,
            const T& value, Compare comp);

(in the January 1996 draft).

It is really unfortunate that the return value is bool.  This
discards information, since in many cases it would be more
useful to return an iterator to the found object, or return last
if no object is found.  The reason is that Compare might only
compare some fields of T, while information might be stored in
the other fields.  Also, this would be more consistent with other
STL algorithms that search: the "not found" condition is signaled
by the return value equaling the end iterator.

This problem came up when I wanted to create a simple array of
structs to hold a keyword-value table and use binary_search to
search it.  It could be made to work easily if binary_search
returned an iterator pointing to the matching object.

It would be possible to use lower_bound, but an extra compare would be
necessary (the iterator points to the least element greater or equal
to the searched-for value, or last if none).  But why is
binary_search inconsistent?  Any better reason than "Stepanov
did it that way"?



--
-- Joe Buck  <jbuck@synopsys.com> (not speaking for Synopsys, Inc)

Work for something because it is good,
not just because it stands a chance to succeed.    -- Vaclav Havel


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Joe Buck (jbuck@Synopsys.COM) wrote:
: binary_search is defined as

: bool binary_search(ForwardIterator first, ForwardIterator last,
:             const T& value);

: or

: bool binary_search(ForwardIterator first, ForwardIterator last,
:             const T& value, Compare comp);

: (in the January 1996 draft).

: It is really unfortunate that the return value is bool.  This
: discards information, since in many cases it would be more
: useful to return an iterator to the found object, or return last
: if no object is found.  The reason is that Compare might only
: compare some fields of T, while information might be stored in
: the other fields.  Also, this would be more consistent with other
: STL algorithms that search: the "not found" condition is signaled
: by the return value equaling the end iterator.

This reminds me of a discussion I had some years
ago with an experienced programmer who always defined
a binary search in an array a[N] with arguments:
 (fisrt=-1, last=N)
 not( first=0, last=N-1)
because it made the logic easier to understand.  This was before
we had lots of text books.

For this to indicate failure be returning 'last':
ForwardIterator binary_search(ForwardIterator first, ForwardIterator last,...)
it is  important that 'last'
can not match the value.
In other words the pre-condition for the search to find the value is
 value lies between first and the object before last inclusive
However the traditional or textbook binary search uses the
following semantics.
 value lies between first and last inclusive.

In my experience people will tend to assume the textbook/trad
version and not read the precise spec.  The errors would be rare.
We would therefore have a breeding ground for bugs.

--
dick botting     http://www.csci.csusb.edu/dick/signature.html
Disclaimer:      CSUSB may or may not agree with this message.
Copyright(1996): Copy freely but say where it came from.
 I have nothing to sell, and I'm giving it away.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]