I was under the impression that in a binary search, the element to be
searched is compared to the middle element and thus the size of the
problem is reduced to half. However, the binary_search() in <algorithm>
takes only forward iterators, so one cannot directly get "the middle
element" . How then does it have O(log(n)) complexity? Or is it that
just traversing the sequence from the first to the last (only
traversing, not comparing) is treated as "free", since the limit is on
the number of comparisons:

Complexity: At most log(last - first) + 2 comparisons. (25.3.3.4 #3)

Also 25.3.3 seems a bit vague:

<quote>
25.3.3 Binary search
All of the algorithms in this section are versions of binary search and
assume that the sequence being searched is in order according to the
implied or explicit comparison function. They work on non-random access
iterators minimizing the number of comparisons, which *will be
logarithmic for all types of iterators*. They are especially
appropriate for random access iterators, because these algorithms do a
logarithmic number of steps through the data structure. For non-random
access iterators they execute a *linear* number of steps.
</quote>
(Emphasis mine)

On one hand it says "which will be logarithmic for all types of
iterators". On the other hand it says "For non-random access iterators
they execute a linear number of steps." Or is it that steps are
different from comparisons?

Prateek Karandikar

--                                                    --
Abstraction is selective ignorance. -Andrew Koenig
--                                                    --

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Prateek wrote:
> I was under the impression that in a binary search, the element to be
> searched is compared to the middle element and thus the size of the
> problem is reduced to half. However, the binary_search() in <algorithm>
> takes only forward iterators, so one cannot directly get "the middle
> element" . How then does it have O(log(n)) complexity? Or is it that
> just traversing the sequence from the first to the last (only
> traversing, not comparing) is treated as "free", since the limit is on
> the number of comparisons:
>
> Complexity: At most log(last - first) + 2 comparisons. (25.3.3.4 #3)
>
> Also 25.3.3 seems a bit vague:
>
> <quote>
> 25.3.3 Binary search
> All of the algorithms in this section are versions of binary search and
> assume that the sequence being searched is in order according to the
> implied or explicit comparison function. They work on non-random access
> iterators minimizing the number of comparisons, which *will be
> logarithmic for all types of iterators*. They are especially
> appropriate for random access iterators, because these algorithms do a
> logarithmic number of steps through the data structure. For non-random
> access iterators they execute a *linear* number of steps.
> </quote>
> (Emphasis mine)
>

The point that isn't being made as clear as it could be here is that you
are guaranteed a logarithmic number of comparisons of the things the
iterators point to, but for non random-access iterators there may be a
linear number of steps through iterators (and actually a linear number
of iterator comparisions).

I agree it's not as clear as it could be...

Chris

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Prateek wrote:
> I was under the impression that in a binary search, the element to be
> searched is compared to the middle element and thus the size of the
> problem is reduced to half. However, the binary_search() in <algorithm>
> takes only forward iterators, so one cannot directly get "the middle
> element" . How then does it have O(log(n)) complexity? Or is it that
> just traversing the sequence from the first to the last (only
> traversing, not comparing) is treated as "free", since the limit is on
> the number of comparisons:
>
> Complexity: At most log(last - first) + 2 comparisons. (25.3.3.4 #3)

In order to find the middle of a range you need first to call distance()
(or equivalent algorithm) to compute the size of the range, then call
advance() (or equivalent algorithm) to get an iterator in middle. If the
range is expressed with forward, non-random iterators, both algorithms
have linear complexity *in the number of iterator increments*. This does
not mean that it's "free" but, rigorously speaking, it does not violate
the complexity requirement of binary_search, which is a statement about
the upper bound of the number of comparisons.

>
> Also 25.3.3 seems a bit vague:

Doesn't seem vague to me... in fact I find it quite precise.

>
> <quote>
> 25.3.3 Binary search
> All of the algorithms in this section are versions of binary search and
> assume that the sequence being searched is in order according to the
> implied or explicit comparison function. They work on non-random access
> iterators minimizing the number of comparisons, which *will be
> logarithmic for all types of iterators*. They are especially
> appropriate for random access iterators, because these algorithms do a
> logarithmic number of steps through the data structure. For non-random
> access iterators they execute a *linear* number of steps.
> </quote>
> (Emphasis mine)
>
> On one hand it says "which will be logarithmic for all types of
> iterators". On the other hand it says "For non-random access iterators
> they execute a linear number of steps." Or is it that steps are
> different from comparisons?
>

Of course the two things are different. The word "steps" refers to "acts
of traversing the data structure" that is, in this case, "iterator
increments". It's quite different from "number of comparisons"!

"Comparisons" relates to values, "steps" relates to traversal. The
standard consistently expresses complexity clauses in terms of operation
on values, while the cost of traversal is either not considered at all
or just referred to in the algorithm description (as in 25.3.3). You may
object to this decision, but it's good enough for me.

Alberto

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Prateek wrote:

> I was under the impression that in a binary search, the element to be
> searched is compared to the middle element and thus the size of the
> problem is reduced to half. However, the binary_search() in
<algorithm>
> takes only forward iterators, so one cannot directly get "the middle
> element" . How then does it have O(log(n)) complexity? Or is it that
> just traversing the sequence from the first to the last (only
> traversing, not comparing) is treated as "free", since the limit is
on
> the number of comparisons:
>
> Complexity: At most log(last - first) + 2 comparisons. (25.3.3.4 #3)
>
> Also 25.3.3 seems a bit vague:
>
> <quote>
> 25.3.3 Binary search
> All of the algorithms in this section are versions of binary search
and
> assume that the sequence being searched is in order according to the
> implied or explicit comparison function. They work on non-random
access
> iterators minimizing the number of comparisons, which *will be
> logarithmic for all types of iterators*. They are especially
> appropriate for random access iterators, because these algorithms do
a
> logarithmic number of steps through the data structure. For
non-random
> access iterators they execute a *linear* number of steps.
> </quote>
> (Emphasis mine)
>
> On one hand it says "which will be logarithmic for all types of
> iterators". On the other hand it says "For non-random access
iterators
> they execute a linear number of steps." Or is it that steps are
> different from comparisons?


Yes. In this context, "steps" refers to incrementing iterators.
Comparisons involve calls to the comparison function. If calls to your
comparison function are sufficiently more expensive than increments to
the iterators, binary_search() can be an advantage over a linear search
even for iterators that aren't random-access.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Prateek wrote:
> I was under the impression that in a binary search, the element to be
> searched is compared to the middle element and thus the size of the
> problem is reduced to half. However, the binary_search() in
<algorithm>
> takes only forward iterators, so one cannot directly get "the middle
> element" . How then does it have O(log(n)) complexity? Or is it that
> just traversing the sequence from the first to the last (only
> traversing, not comparing) is treated as "free", since the limit is
on
> the number of comparisons:
>
> Complexity: At most log(last - first) + 2 comparisons. (25.3.3.4 #3)
>
> Also 25.3.3 seems a bit vague:
>
> <quote>
> 25.3.3 Binary search
> All of the algorithms in this section are versions of binary search
and
> assume that the sequence being searched is in order according to the
> implied or explicit comparison function. They work on non-random
access
> iterators minimizing the number of comparisons, which *will be
> logarithmic for all types of iterators*. They are especially
> appropriate for random access iterators, because these algorithms do
a
> logarithmic number of steps through the data structure. For
non-random
> access iterators they execute a *linear* number of steps.
> </quote>
> (Emphasis mine)
>
> On one hand it says "which will be logarithmic for all types of
> iterators". On the other hand it says "For non-random access
iterators
> they execute a linear number of steps." Or is it that steps are
> different from comparisons?
>

Yes, number of comparisons means what it means while number of
steps means the number of iterators' ++ (for forward iterators) or
+= (for RAI) operations. Actually (at least in mine implementation,
check yours,
but I bet the same) binary_search is implemented in terms of
lower_bound, which is
itself implemented in terms of 'distance' and 'advance', each of which
are invoked
logarithmic number of times. These operations behave differently for
different kind
of iterators, having linear complexity for forward and quite no
(constant) complexity
for random access iterators.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]