beginner help with sequential and binary search

R

Ray Leon

Dear Sirs or Madam:

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)



Answer below:



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)



Answer below:



Sequential search - Seven (7)

Binary search - Two (2)



Thanks



Ray
 
W

Willem

Ray Leon wrote:
) Dear Sirs or Madam:
)
) 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
 
G

Gene

Dear Sirs or Madam:

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)

Answer below:

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)

Answer below:

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.
 
J

Juha Nieminen

Ray 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:

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)

Answer below:

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)

Answer below:

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.
 
G

Gene

  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).







  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.
 
P

popeyerayaz

  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).
  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].
3 comparisons were made.

Searching for value 2 in array.
Value 2, found in array[1].
2 comparisons were made.

Searching for value 3 in array.
Value 3, found in array[2].
3 comparisons were made.

Searching for value 4 in array.
Value 4, found in array[3].
1 comparisons were made.

Searching for value 5 in array.
Value 5, found in array[4].
3 comparisons were made.

Searching for value 6 in array.
Value 6, found in array[5].
2 comparisons were made.

Searching for value 7 in array.
Value 7, found in array[6].
3 comparisons were made.

/* 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"
                 "%d comparisons were made.\n"
                 , target[index]
                 , found - array, Comps);
         } else {
             printf("Value %d, not found in array.\n"
                 "%d comparisons were made.\n"
                 , 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 */

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)

Answer below:

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.
 
B

Ben Bacarisse

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)

Answer below:

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
case where writing lots might help you out.
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
about it!).
 
J

Juha Nieminen

Gene said:
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.
 
J

Juha Nieminen

pete said:
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.
 
B

Ben Bacarisse

Lew said:
popeyerayaz said:
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).
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.
 
C

conrad

Ben said:
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.
 
J

Juha Nieminen

Dann said:
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.
 
B

Ben Bacarisse

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/


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.
 
R

Ray Leon

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 said:
Lew said:
popeyerayaz said:
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).
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.
 
U

user923005

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.
 
B

Ben Bacarisse

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 said:
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.
Ben Bacarisse wrote:
It looks fine to me.
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.]
 
J

Juha Nieminen

pete said:
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.
 
J

Juha Nieminen

Dann said:
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.
 
J

Juha Nieminen

Dann said:
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).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top