# beginner help with sequential and binary search

Discussion in 'Java' started by Ray Leon, Jul 10, 2008.

1. ### Ray LeonGuest

I have completed a quiz and just want feedback on any possible mistake I
have made if any. Any help is greatly appreciated. I think I have the
correct answers for the following questions:

1. Let myArray represents an array of 5 elements with the following values
in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
the element 30 (the third element) using:

a. Sequential search (10 points)

b. Binary search (10 points)

Sequential search - Three (3)

Binary search - One (1)

2. Consider the array consisting of 7 elements sorted in ascending order.
What is the Maximum number of comparisons that need to be done to find any
given element using:

a. Sequential search (10 points)

b. Binary search (10 points)

Sequential search - Seven (7)

Binary search - Two (2)

Thanks

Ray

Ray Leon, Jul 10, 2008

2. ### WillemGuest

Ray Leon wrote:
)
) I have completed a quiz and just want feedback on any possible mistake I
) have made if any. Any help is greatly appreciated. I think I have the
) correct answers for the following questions:

It would be helpful if you would give not only the answers,
but also the reasoning that you used to get this answer.

By the way: You got one of the last two answers wrong.
Which one is the wrong one depends on a detail that was
not given in the question.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Jul 10, 2008

3. ### GeneGuest

On Jul 10, 2:35 pm, "Ray Leon" <> wrote:
>
> I have completed a quiz and just want feedback on any possible mistake I
> have made if any. Any help is greatly appreciated. I think I have the
> correct answers for the following questions:
>
> 1. Let myArray represents an array of 5 elements with the following values
> in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
> the element 30 (the third element) using:
>
> a. Sequential search (10 points)
>
> b. Binary search (10 points)
>
>
> Sequential search - Three (3)
>
> Binary search - One (1)
>
> 2. Consider the array consisting of 7 elements sorted in ascending order.
> What is the Maximum number of comparisons that need to be done to find any
> given element using:
>
> a. Sequential search (10 points)
>
> b. Binary search (10 points)
>
>
> Sequential search - Seven (7)
>
> Binary search -  Two (2)
>

It's fairly likely you've given close the desired answers. But the
devil is in the details.

1) Are your algorithms required to reject searches for items that
aren't there? If so, then, for example, the last answer is (at least)
3. If not, then the second last answer is 6 (i.e. if you've checked 6
items and it has to be in the list, then it must be the 7th.

2) What is a "comparison?" Most programming languages don't provide 3-
way branches for <, =, >, so each pass through the binary search loop
actually requires _two_ comparisons: one for strict equality and one
for inequality. It's the same if you decide to implement linear
search that "quits early" because the array is sorted.

3) Again if the search item might not be found, then the
implementation of linear search becomes a bit tricky because you might
run off then end of the list. You can solve this efficiently - with
just one extra comparison - by adding a "sentinel" item at the end
that's equal to the key. Or you can use a separate counter, but that
adds one comparison _per iteration_ of the search loop.

Gene, Jul 10, 2008
4. ### Juha NieminenGuest

Ray Leon wrote:
> I have completed a quiz and just want feedback on any possible mistake I
> have made if any. Any help is greatly appreciated. I think I have the
> correct answers for the following questions:
>
> 1. Let myArray represents an array of 5 elements with the following values
> in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
> the element 30 (the third element) using:
>
> a. Sequential search (10 points)
>
> b. Binary search (10 points)
>
>
> Sequential search - Three (3)
>
> Binary search - One (1)

The answer may not be that simple because "binary search" is not a
completely unambiguous term. More precisely, you have to state what
happens if the binary search is performed on an array which may contain
repeated values: Should the binary search just tell whether the element
exists in the array, or if there's more than one such element, should it
return a handle to the first one in the array?

If "binary search" means "tell me if this element exists in the
array", then the answer of 1 is correct. However, if it means "give me a
handle to the first appearance of this element in the array", then the
correct answer becomes 3 (because the binary search needs to be
continued even if an element with the same value is found immediately).

> 2. Consider the array consisting of 7 elements sorted in ascending order.
> What is the Maximum number of comparisons that need to be done to find any
> given element using:
>
> a. Sequential search (10 points)
>
> b. Binary search (10 points)
>
>
> Sequential search - Seven (7)
>
> Binary search - Two (2)

Even if we are only checking for the existence of the element in the
array, the binary search would require in the worst case 4 comparisons:
the first comparison checks the fourth element, then, assuming that
element is too small, it checks the fifth element (because the middle of
4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
also too small, it checks the sixth element (which is the middle of 5
and 7), and if that also was too small, finally the seventh.

Juha Nieminen, Jul 10, 2008
5. ### GeneGuest

On Jul 10, 4:56 pm, Juha Nieminen <> wrote:
> Ray Leon wrote:
> > I have completed a quiz and just want feedback on any possible mistake I
> > have made if any. Any help is greatly appreciated. I think I have the
> > correct answers for the following questions:

>
> > 1. Let myArray represents an array of 5 elements with the following values
> > in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
> > the element 30 (the third element) using:

>
> > a. Sequential search (10 points)

>
> > b. Binary search (10 points)

>

>
> > Sequential search - Three (3)

>
> > Binary search - One (1)

>
>   The answer may not be that simple because "binary search" is not a
> completely unambiguous term. More precisely, you have to state what
> happens if the binary search is performed on an array which may contain
> repeated values: Should the binary search just tell whether the element
> exists in the array, or if there's more than one such element, should it
> return a handle to the first one in the array?
>
>   If "binary search" means "tell me if this element exists in the
> array", then the answer of 1 is correct. However, if it means "give me a
> handle to the first appearance of this element in the array", then the
> correct answer becomes 3 (because the binary search needs to be
> continued even if an element with the same value is found immediately).
>
> > 2. Consider the array consisting of 7 elements sorted in ascending order.
> > What is the Maximum number of comparisons that need to be done to find any
> > given element using:

>
> > a. Sequential search (10 points)

>
> > b. Binary search (10 points)

>

>
> > Sequential search - Seven (7)

>
> > Binary search -  Two (2)

>
>   Even if we are only checking for the existence of the element in the
> array, the binary search would require in the worst case 4 comparisons:
> the first comparison checks the fourth element, then, assuming that
> element is too small, it checks the fifth element (because the middle of
> 4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
> also too small, it checks the sixth element (which is the middle of 5
> and 7), and if that also was too small, finally the seventh.- Hide quoted text -
>
> - Show quoted text -

I can't get 4. The first comparison looks at the 4th element. Either
it's successful or it rejects 4 elements, leaving 3. The second
comparison looks at the middle of the 3. Either it's successful or it
rejects 2 elements, which leaves 1. The question is whether a 3rd
comparison is needed to check for a match because the searched-for
element might be missing altogether. So it's either 2 or 3.

Gene, Jul 11, 2008
6. ### popeyerayazGuest

On Jul 10, 6:38 pm, pete <> wrote:
> Juha Nieminen wrote:
> > Ray Leon wrote:
> >> I have completed a quiz and just want feedback on any possible mistake I
> >> have made if any. Any help is greatly appreciated. I think I have the
> >> correct answers for the following questions:

>
> >> 1. Let myArray represents an array of 5 elements with the following values
> >> in this order: 10, 20, 30, 40, 50. How many comparisons does it take to find
> >> the element 30 (the third element) using:

>
> >> a. Sequential search (10 points)

>
> >> b. Binary search (10 points)

>

>
> >> Sequential search - Three (3)

>
> >> Binary search - One (1)

>
> >   The answer may not be that simple because "binary search" is not a
> > completely unambiguous term. More precisely, you have to state what
> > happens if the binary search is performed on an array which may contain
> > repeated values: Should the binary search just tell whether the element
> > exists in the array, or if there's more than one such element, should it
> > return a handle to the first one in the array?

>
> >   If "binary search" means "tell me if this element exists in the
> > array", then the answer of 1 is correct. However, if it means "give me a
> > handle to the first appearance of this element in the array", then the
> > correct answer becomes 3 (because the binary search needs to be
> > continued even if an element with the same value is found immediately).

>
> >> 2. Consider the array consisting of 7 elements sorted in ascending order.
> >> What is the Maximum number of comparisons that need to be done to find any
> >> given element using:

>
> >> a. Sequential search (10 points)

>
> >> b. Binary search (10 points)

>

>
> >> Sequential search - Seven (7)

>
> >> Binary search -  Two (2)

>
> >   Even if we are only checking for the existence of the element in the
> > array, the binary search would require in the worst case 4 comparisons:
> > the first comparison checks the fourth element, then, assuming that
> > element is too small, it checks the fifth element (because the middle of
> > 4 and 7 is 5.5, which gets rounded eg. to 5), then assuming that one is
> > also too small, it checks the sixth element (which is the middle of 5
> > and 7), and if that also was too small, finally the seventh.

>
> That is wrong.
> If it were element 7,
> the binary search pattern would be 4,6,7.
>
> Incrementing from 4 to 7,
> just obviously isn't binary search.
>
> /* BEGIN new.c output */
>
> int array[] = {1,2,3,4,5,6,7};
>
> Searching for value 1 in array.
> Value 1, found in array[0].
>
> Searching for value 2 in array.
> Value 2, found in array[1].
>
> Searching for value 3 in array.
> Value 3, found in array[2].
>
> Searching for value 4 in array.
> Value 4, found in array[3].
>
> Searching for value 5 in array.
> Value 5, found in array[4].
>
> Searching for value 6 in array.
> Value 6, found in array[5].
>
> Searching for value 7 in array.
> Value 7, found in array[6].
>
> /* END new.c output */
>
> /* BEGIN new.c */
>
> #include <stdio.h>
>
> #define NMEMB(A)        (sizeof(A) / sizeof *(A))
>
> int Comps;
>
> void *b_search(const void *key, const void *base,
>                 size_t nmemb, size_t size,
>                 int (*compar)(const void *, const void *));
> int comparison(const void *arg1, const void *arg2);
>
> int main(void)
> {
>      int array[] = {1,2,3,4,5,6,7};
>      const int target[] = {1,2,3,4,5,6,7};
>      unsigned index;
>      int *found;
>
>      puts("/* BEGIN new.c output */\n");
>      puts("int array[] = {1,2,3,4,5,6,7};\n");
>      for (index = 0; index != NMEMB(target); ++index) {
>          Comps = 0;
>          printf("Searching for value %d in array.\n", target[index]);
>          found = b_search(target + index, array, NMEMB(array)
>              , sizeof*array, comparison);
>          if (found != NULL) {
>              printf("Value %d, found in array[%u].\n"
>                  , target[index]
>                  , found - array, Comps);
>          } else {
>                  , target[index], Comps);
>          }
>          putchar('\n');
>      }
>      puts("/* END new.c output */");
>      return 0;
>
> }
>
> void *b_search(const void *key, const void *base,
>                 size_t nmemb, size_t size,
>                 int (*compar)(const void *, const void *))
> {
>      int comp;
>      size_t middle, high, low;
>      const unsigned char *array, *found;
>
>      found = NULL;
>      if (nmemb != 0) {
>          array = base;
>          low = 0;
>          high = nmemb;
>          do {
>              nmemb = high - low;
>              middle = nmemb / 2 + low;
>              base = middle * size + array;
>              comp = compar(key, base);
>              if (comp > 0) {
>                  low = middle;
>              } else {
>                  high = middle;
>                  if (comp == 0) {
>                      found = base;
>                      break;
>                  }
>              }
>          } while (nmemb != 1);
>      }
>      return (void *)found;
>
> }
>
> int comparison(const void *arg1, const void *arg2)
> {
>      ++Comps;
>      return *(const int *)arg2  > *(const int *)arg1 ? -1
>           : *(const int *)arg2 != *(const int *)arg1;
>
> }
>
> /* END new.c */
>
> --
> pete

2. Consider the array consisting of 7 elements sorted in ascending
order. What is the Maximum number of comparisons that need to be done
to find any given element using:

a. Sequential search (10 points)
b. Binary search (10 points)

a. Since the total number of elements is seven, and the value is
unknown I can only assume that the maximum number of comparisons may
be the total amount of elements, seven (7).

b. The binary search for any given number is what I can’t figure out.
I have attempted to use the following code and formula but am very
confused as to what the answer could be. I can get certain values but
when I try for example the number two as the value to search for it
just doesn’t work.

low = 0
high = N
while (low < high) {
mid = (low + high)/2;
if (A[mid] < value)
low = mid + 1;
else
//can't be high = mid-1: here A[mid] >= value,
//so high can't be < mid if A[mid] == value
high = mid;
}

if (low < N) and (A[low] == value)
return low
else
return not_found

any help greatly appreciated.

popeyerayaz, Jul 11, 2008
7. ### Ben BacarisseGuest

popeyerayaz <> writes:

<snip all of pete's post -- you don't seem to be replying to it>

> 2. Consider the array consisting of 7 elements sorted in ascending
> order. What is the Maximum number of comparisons that need to be done
> to find any given element using:
>
> a. Sequential search (10 points)
> b. Binary search (10 points)
>
>
> a. Since the total number of elements is seven, and the value is
> unknown I can only assume that the maximum number of comparisons may
> be the total amount of elements, seven (7).

Depending on the exact meaning of the question, this is probably
wrong. If comparisons means "element comparisons" (i.e. any tests
required to run the loop are excluded) then you can find an element
that _you know is there_ with N-1 tests in sequence:

for i in 1..N-1 do
if element = value
return i
return N

but the error is probably in the wording of the question. This is a

> b. The binary search for any given number is what I canâ€™t figure out.
> I have attempted to use the following code and formula but am very
> confused as to what the answer could be. I can get certain values but
> when I try for example the number two as the value to search for it
> just doesnâ€™t work.
>
> low = 0
> high = N
> while (low < high) {
> mid = (low + high)/2;
> if (A[mid] < value)
> low = mid + 1;
> else
> //can't be high = mid-1: here A[mid] >= value,
> //so high can't be < mid if A[mid] == value
> high = mid;
> }
>
> if (low < N) and (A[low] == value)
> return low
> else
> return not_found
>
> any help greatly appreciated.

It looks fine to me. Maybe what you are running is not quite the same
code (or maybe I've missed a bug in it, but I tested it *and* reasoned

--
Ben.

Ben Bacarisse, Jul 11, 2008
8. ### Juha NieminenGuest

Gene wrote:
> I can't get 4. The first comparison looks at the 4th element. Either
> it's successful or it rejects 4 elements, leaving 3.

You can't do that with one single comparison. In order to do that you
would have to first look if the 4th element is equal to the searched
element, and if it isn't, then you have to look if it's smaller (in
order to decide which half you discard), after which you can continue
with the correct half without the 4th element included.
That would make two comparisons per step. The total number of
comparisons in the worst case would grow to at least 5 (depending on how
you implement the check for a range of one single element).

In order to have only one comparison per step, you have to look if the
4th element is smaller than the searched element, and then choose the
correct half *including* that 4th element. (You can't discard it because
it might actually be the searched element.)
That is, the first step discards 3 elements and continues with the
remaining 4.
This way the total number of comparisons in the worst case is 4.

Juha Nieminen, Jul 11, 2008
9. ### Juha NieminenGuest

pete wrote:
> if (comp > 0) {
> low = middle;
> } else {
> high = middle;
> if (comp == 0) {

You are making *two* comparisons per step here, thus doubling the
total number of comparisons.

Juha Nieminen, Jul 11, 2008
10. ### Ben BacarisseGuest

Lew <> writes:

> popeyerayaz <> writes:
>>> low = 0
>>> high = N
>>> while (low < high) {
>>> mid = (low + high)/2;
>>> if (A[mid] < value)
>>> low = mid + 1;
>>> else
>>> //can't be high = mid-1: here A[mid] >= value,
>>> //so high can't be < mid if A[mid] == value
>>> high = mid;
>>> }
>>>
>>> if (low < N) and (A[low] == value)
>>> return low
>>> else
>>> return not_found
>>>
>>> any help greatly appreciated.

>
> Weird to see C code in a message thread that was apparently geared to
> the Java community.

Actually it is not C either. I assumed it was pseudo-code (though it
is not a million miles from either, style issues aside).

> Ben Bacarisse wrote:
>> It looks fine to me. Maybe what you are running is not quite the same
>> code (or maybe I've missed a bug in it, but I tested it *and* reasoned

>
> As long as both low and high stay below Integer.MAX_VALUE/2, or to put
> it another way, as long as the value position is below
> Integer.MAX_VALUE/2.

Not if you do, as I did, and turn the pseudo-code into C with low and
high unsigned (size_t is a good choice). Then you get no overflow
issues. A good values for "not_found" is then N.

I don't know if Java has a non-overflowing integer type.

--
Ben.

Ben Bacarisse, Jul 11, 2008
11. ### Guest

Lew writes:
> > As long as both low and high stay below Integer.MAX_VALUE/2, or to put
> > it another way, as long as the value position is below
> > Integer.MAX_VALUE/2.

Ben Bacarisse wrote:
> Not if you do, as I did, and turn the pseudo-code into C with low and
> high unsigned (size_t is a good choice).  Then you get no overflow
> issues.  A good values for "not_found" is then N.

Given the OP's original distribution to a Java newsgroup and not a C
newsgroup, I looked at the problem strictly from a Java perspective/

> I don't know if Java has a non-overflowing integer type.

It does not, by design.

But surely size_t does overflow in C? Unsignedness doesn't prevent
overflow, it just shifts the trouble point.

--
Lew

, Jul 11, 2008
12. ### Juha NieminenGuest

Dann Corbit wrote:
> "Juha Nieminen" <> wrote in message
> news:aqKdk.128\$...
>> pete wrote:
>>> if (comp > 0) {
>>> low = middle;
>>> } else {
>>> high = middle;
>>> if (comp == 0) {

>> You are making *two* comparisons per step here, thus doubling the
>> total number of comparisons.

>
> No. He is using the value returned by the comparison function twice.

That doesn't matter, because the comparison function needs to make
internally (at least) two comparisons to be able to return -1, 0 or 1.
The piece of code I quoted simply highlighted this fact.

> Your distinction might be important if the comparison operation is very
> cheap

In this particular case the original questions asked how many
comparisons are required. I consider "<" and "==" to be *two*
comparisons, even if they are applied to the same values.

The distinction is relevant because binary search can be implemented
with only one comparison (<) per step (in fact, equality comparison is
not needed at all in order to implement a fully-working binary search).
Thus this distinction is quite relevant with regard to the original
questions.

Juha Nieminen, Jul 12, 2008
13. ### Ben BacarisseGuest

writes:

> Lew writes:
>> > As long as both low and high stay below Integer.MAX_VALUE/2, or to put
>> > it another way, as long as the value position is below
>> > Integer.MAX_VALUE/2.

>
> Ben Bacarisse wrote:
>> Not if you do, as I did, and turn the pseudo-code into C with low and
>> high unsigned (size_t is a good choice). Â Then you get no overflow
>> issues. Â A good values for "not_found" is then N.

>
> Given the OP's original distribution to a Java newsgroup and not a C
> newsgroup, I looked at the problem strictly from a Java perspective/
>
>> I don't know if Java has a non-overflowing integer type.

>
> It does not, by design.
>
> But surely size_t does overflow in C? Unsignedness doesn't prevent
> overflow, it just shifts the trouble point.

Well it does (prevent overflow) but that is a matter of C's particular
terminology. C's unsigned types don't "overflow" because that term
is reserved for what happens to other types like signed ints.

You are quite right that writing:

size_t low = 0, high = N;
...
size_t mid = (low + high)/2;

shifts the problem. It is now not "overflow" (which in C can cause
pretty much anything) but getting -- absolutely predictably -- the
wrong answer! The canonical way to write this correctly is:

size_t mid = low + (high - low)/2;

I got too hung up on the word to see what you were getting at and,
frankly, I should have got it right away. It is, quite literally, one
of the oldest bugs around.

The original posted code isn't really wrong. If it can be seem as
pseudo code the arithmetic might be mathematical arithmetic.

--
Ben.

Ben Bacarisse, Jul 12, 2008
14. ### Ray LeonGuest

I did run the code that Pete created. The actual book is a beginners
programming text, and is pseudocode. Can I assume that since the problem
states
2. Consider the array consisting of 7 elements sorted in ascending order.
What is the Maximum number of comparisons that need to be done to find any
given element using:

a. Sequential search (10 points)
b. Binary search (10 points)
The key word being ANY GIVEN ELEMENT so the Pete's code I ran and looks like
it ran eight (8) comparisons. I assume that my answer should be seven (7)
since the array should only consist of seven elements.

Ray

"Ben Bacarisse" <> wrote in message
news:...
> Lew <> writes:
>
>> popeyerayaz <> writes:
>>>> low = 0
>>>> high = N
>>>> while (low < high) {
>>>> mid = (low + high)/2;
>>>> if (A[mid] < value)
>>>> low = mid + 1;
>>>> else
>>>> //can't be high = mid-1: here A[mid] >= value,
>>>> //so high can't be < mid if A[mid] == value
>>>> high = mid;
>>>> }
>>>>
>>>> if (low < N) and (A[low] == value)
>>>> return low
>>>> else
>>>> return not_found
>>>>
>>>> any help greatly appreciated.

>>
>> Weird to see C code in a message thread that was apparently geared to
>> the Java community.

>
> Actually it is not C either. I assumed it was pseudo-code (though it
> is not a million miles from either, style issues aside).
>
>> Ben Bacarisse wrote:
>>> It looks fine to me. Maybe what you are running is not quite the same
>>> code (or maybe I've missed a bug in it, but I tested it *and* reasoned

>>
>> As long as both low and high stay below Integer.MAX_VALUE/2, or to put
>> it another way, as long as the value position is below
>> Integer.MAX_VALUE/2.

>
> Not if you do, as I did, and turn the pseudo-code into C with low and
> high unsigned (size_t is a good choice). Then you get no overflow
> issues. A good values for "not_found" is then N.
>
> I don't know if Java has a non-overflowing integer type.
>
> --
> Ben.

Ray Leon, Jul 12, 2008
15. ### user923005Guest

On Jul 11, 10:22 pm, (Richard Harter) wrote:
> On Fri, 11 Jul 2008 19:39:55 -0700, "Dann Corbit"
>
>
>
>
>
> <> wrote:
> >"Richard Harter" <> wrote in message
> >news:...
> >> On Fri, 11 Jul 2008 18:15:14 -0700, "Dann Corbit"
> >> <> wrote:

>
> >>>"Lew" <> wrote in message
> >>>news:...
> >>>> Juha Nieminen wrote:
> >>>> pete wrote:
> >>>>>>>>             if (comp > 0) {

>
> >>>> 'if' => comparison number one.

>
> >>>>>>>>                 low = middle;
> >>>>>>>>             } else {
> >>>>>>>>                 high = middle;
> >>>>>>>>                 if (comp == 0) {

>
> >>>> 'if' => comparison number two.

>
> >>>> "Juha Nieminen" wrote ...
> >>>>>>>  You are making *two* comparisons per step here, thus doubling the
> >>>>>>> total number of comparisons.

>
> >>>> Dann Corbit wrote:
> >>>>>> No.  He is using the value returned by the comparison function twice.

>
> >>>> In two comparisons.

>
> >>>> It's pretty obvious.

>
> >>>In sorting, the comparison count is the number of times the comparison
> >>>function is called.  I can obviously see how decisions have been made with
> >>>the return of the comparison function.

>
> >> With all due respect, this just won't do.  Yes, you can count the
> >> number of calls to a comparison function, and that is a
> >> convenient thing to do.  Quite often that is the appropriate
> >> thing to do.  Still, a ternary valued comparison function
> >> delivers log2(3) bits of information rather than one bit.  What
> >> you are doing in the code is exploiting the fact that the cost of
> >> doing comparisons on that ternary value might be cheap compared
> >> to the cost of doing comparisons on the original data, and that
> >> quite often detecting equality during the course of a comparison
> >> is cheap.  These considerations are programming tricks rather
> >> than mathematics.

>
> >Using a ternary comparison is standard in the C language and expected by
> >standard library functions.

>
> [snip quotations from manuals]
>
> I'm sorry, I actually roared with laughter when reading your
> response.  Bad of me, of course, but still.  This thread is not
> posted to comp.lang.c, it is a thread that is cross posted to
> comp.programming and comp.lang.java.programmer.  The
> idiosyncracies of the C language are only marginally relevant,
> and doing computer science does not consist of quoting from
> language manuals.

It was nothing more than an explanation of why a tertiary comparison
is not surprising.

user923005, Jul 12, 2008
16. ### Ben BacarisseGuest

Please don't top-post. I've edited out most of the message you
replied to and moved you comments to the bottom.

"Ray Leon" <> writes:
> "Ben Bacarisse" <> wrote in message
> news:...

<snip>
>>> popeyerayaz <> writes:
>>>>> low = 0
>>>>> high = N
>>>>> while (low < high) {
>>>>> mid = (low + high)/2;
>>>>> if (A[mid] < value)
>>>>> low = mid + 1;
>>>>> else
>>>>> //can't be high = mid-1: here A[mid] >= value,
>>>>> //so high can't be < mid if A[mid] == value
>>>>> high = mid;
>>>>> }
>>>>>
>>>>> if (low < N) and (A[low] == value)
>>>>> return low
>>>>> else
>>>>> return not_found
>>>>>
>>>>> any help greatly appreciated.

<snip>
>>> Ben Bacarisse wrote:
>>>> It looks fine to me.

<snip>
> I did run the code that Pete created. The actual book is a beginners
> programming text, and is pseudocode. Can I assume that since the
> problem states
> 2. Consider the array consisting of 7 elements sorted in ascending
> order. What is the Maximum number of comparisons that need to be done
> to find any given element using:
>
> a. Sequential search (10 points)
> b. Binary search (10 points)
> The key word being ANY GIVEN ELEMENT so the Pete's code I ran and
> looks like it ran eight (8) comparisons. I assume that my answer
> should be seven (7) since the array should only consist of seven
> elements.

Pete's code was slightly differently organised but I don't see how you
get 8. It is usual to count only the comparisons between elements and
not to add in those involving counters etc that are there just to run
the loops and so on. Is that what you are counting?

[I've set followup-to: comp.programming since this is not really about
Java as far as I can see.]

--
Ben.

Ben Bacarisse, Jul 12, 2008
17. ### Roedy GreenGuest

On Thu, 10 Jul 2008 11:35:21 -0700, "Ray Leon" <>
wrote, quoted or indirectly quoted someone who said :

>
>I have completed a quiz and just want feedback on any possible mistake I
>have made if any. Any help is greatly appreciated. I think I have the
>correct answers for the following questions:

see http://mindprod.com/jgloss/binarysearch.html

Write the code, and add instrumentation to count how often compare is
called.

http://mindprod.com/jgloss/comparable.html
--

The Java Glossary
http://mindprod.com

Roedy Green, Jul 12, 2008
18. ### Juha NieminenGuest

pete wrote:
> I can't can't get as many as 4 to find any element either.

Because you are not counting all the comparisons you are making.

> if (A[mid] < value) {
> low = mid;
> } else {
> high = mid;
> if (A[mid] == value) {

You are making *two* comparisons there, not one.

Juha Nieminen, Jul 12, 2008
19. ### Juha NieminenGuest

Dann Corbit wrote:
> So when you want to know how many comparisons a sort or search is
> performing, you count every relational operator used in the program?

No, you count the number of comparisons applied to the elements of the
array. In all these examples *two* comparisons with the elements of the
array are performed at each step.

One suggestion cleverly tried to disguise the comparison into looking
just like one by making it a function call which performs the comparison
with the array element. However, the function in question must use at
least two comparisons with the element in order to be able to return one
of three possible values.

Again: Binary search *can* be implemented with one single comparison
per step. The equality comparison is not strictly needed.

Juha Nieminen, Jul 12, 2008
20. ### Juha NieminenGuest

Dann Corbit wrote:
> To Juha:
> He could have written comparison as:
>
> int comparison(const void *arg1, const void *arg2)
> {
> ++Comps;
> return *(const int *)arg2 - *(const int *)arg1;
> }

That can only be applied if you know the elements are integers.

I understood the original questions to be more generic in nature, and
the given arrays using integers to be just an example. You could
substitute the integers with anything else that can be comparable for
inequality.

You can't make a generic binary search which assumes you can perform a
substraction of the elements. The only thing you can assume is that you
can compare if one of them is less than the other.

The fact remains, if you want to compare for < and ==, that makes two
comparisons, and a binary search does not really need the latter, so
it's possible to implement it with just one comparison per step (and
thus the worst-case total number of comparisons is smaller, at least
from a certain array size up).

Juha Nieminen, Jul 12, 2008