Reply to thread

Message

[QUOTE="Gene, post: 3586456"]
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.
[/QUOTE]

Verification