B
Ben Bacarisse
Juha Nieminen said: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.]