beginner help with sequential and binary search

[Ben Bacarisse]

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.

Just to be clear (this thread is getting messy with unquoted code
being discussed) not all the examples do what you say. The original
pseudo code (tidied up) was:

low = 0;
high = N;
while low < high {
mid = low + (high - low)/2;
if (A[mid] < value)
low = mid + 1;
else high = mid;
}
if (low < N) and (A[low] == value)
return low;
else return not_found;

This has an extra == test to confirm membership, but does not do two
element comparisons at each step. If the question is taken literally
(and we are to count comparisons needed to find an element we know is
there) then this last test can be removed. We end up with

low = 0;
high = N;
while low < high {
mid = low + (high - low)/2;
if (A[mid] < value)
low = mid + 1;
else high = mid;
}
return low;

which will do no more than 3 element comparisons to find any element
in a 7 element array. I think you said 4, presumably because you took
the question to be badly worded. It is more usual to ask how many
element comparisons are needed to find out *if* a given value is
present in a sorted list.

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

Do you mean as in the original posted pseudo code, or did you have
another algorithm in mind? Can the final == test be eliminated (other
than by rewriting as !(A[min] > value) or A[min] <= value) -- i.e. can
the while thing be done with one kind of test? That would be rather
elegant, but I can't see a way to that.

[Again, I've set followups. I don't read the Java groups, but it
seems unlikely that purely algorithmic questions are topical there.]

 

[Patricia Shanahan]

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.

Did the exact pseudo-code from the book get posted? It is possible to
give a computational complexity for a general algorithm idea, such as
"binary search", but an exact comparison count has to be for the
specific code.

Patricia

 

[CBFalconer]

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.

You can always create a safe comparison (under C rules) with:

return (a < b) - (b < a);

returning 1, 0, or -1 for greater, equal, less. No overflow. More
parentheses are needed if a and/or b can be (overflow free)
expressions.

 

[Ben Bacarisse]

Did the exact pseudo-code from the book get posted?

Not at first.

It is possible to
give a computational complexity for a general algorithm idea, such as
"binary search", but an exact comparison count has to be for the
specific code.

A while later, the OP posted:

low = 0;
high = N;
while low < high {
mid = (low + high)/2;
if (A[mid] < value)
low = mid + 1;
else high = mid;
}
if (low < N) and (A[low] == value)
return low;
else return not_found;

[Layout and syntax edited. Followups set.]

 

[Juha Nieminen]

You can always create a safe comparison (under C rules) with:

return (a < b) - (b < a);

Have you counted the number of comparisons there?

 

[John W Kennedy]

(e-mail address removed) said:



No, it can't, because it's an unsigned type.


In C it does, because in C all unsigned integer arithmetic results are
reduced modulo (max_value* + 1) until they are in range for the type.

*where "max_value" means the largest value representable in the type.

When they added unsigned types in Ada '95, they did them as "modulo"
types (but generalized to moduli other than powers of two).