Velocity Reviews > Java > beginner help with sequential and binary search

# beginner help with sequential and binary search

Ray Leon
Guest
Posts: n/a

 07-10-2008

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

Willem
Guest
Posts: n/a

 07-10-2008
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

Gene
Guest
Posts: n/a

 07-10-2008
On Jul 10, 2:35*pm, "Ray Leon" <(E-Mail Removed)> 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.

Juha Nieminen
Guest
Posts: n/a

 07-10-2008
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.

Gene
Guest
Posts: n/a

 07-11-2008
On Jul 10, 4:56*pm, Juha Nieminen <(E-Mail Removed)> 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.

popeyerayaz
Guest
Posts: n/a

 07-11-2008
On Jul 10, 6:38*pm, pete <(E-Mail Removed)> 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"
> * * * * * * * * *"%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 */
>
> --
> 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.

Ben Bacarisse
Guest
Posts: n/a

 07-11-2008
popeyerayaz <(E-Mail Removed)> 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[i] = 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.

Juha Nieminen
Guest
Posts: n/a

 07-11-2008
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
Guest
Posts: n/a

 07-11-2008
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.

Ben Bacarisse
Guest
Posts: n/a

 07-11-2008
Lew <(E-Mail Removed)> writes:

> popeyerayaz <(E-Mail Removed)> 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.