Assignment 3: Question 3

This may sound dumb but I'm confused by the second part of question 3. Isn't a sequential search for ordered lists exactly the same as a sequential search for unordered lists? In which case the answer is exactly the same as the code already given to sort an unordered list?

A sequential search on an ordered list could possibly be more efficient because you don't have to go through the entire list to find that the search item is not in the list.

Aaaah! A lightbulb has gone on...

Thanks for the hint

brettc Wrote:
-------------------------------------------------------
> A sequential search on an ordered list could
> possibly be more efficient because you don't have
> to go through the entire list to find that the
> search item is not in the list.


Then again it depends if the item being searched for is not the last item in an ordered list ...

hmmm...good point

Yes, but that is an edge case. The general case is that the item being searched for is somewhere in the middle. And because the items are ordered, you only have to travel so far in the list before deciding that the item won't be found in the remainder of the list.

Then again it depends if the item being searched for is not the 2nd last item in an ordered list ...

Why is the second item a special case?

brettc Wrote:
-------------------------------------------------------
> A sequential search on an ordered list could
> possibly be more efficient because you don't have
> to go through the entire list to find that the
> search item is not in the list.

I am referring to the position of the item being searched for in an ordered list ;eg.

if you have 1000 items in an ordered list and the item being searched for sequentially is the 2nd last item then 99 comparisons will have to be done AND
if you have 1000 items in a non-ordered list and the item being searched for sequentially is the 2nd last item then 99 comparisons will also have to be done.
So i don't think that the sequential search is more efficient because it depends on the position of the item in the list.

( This is why the binary search is more efficient if you have an ordered list ) .. anyone disagree ??

I don't disagree, binary search is more efficient on an ordered list...

I should have been more clear I guess, I meant that a sequential search on an ordered list could be more efficient than a sequential search on an unordered list, but not more efficient than a binary search

You cannot use a binary search on an unordered list. If the list is unordered, you can only resort to a sequencial search. In which case, on average, you'll search half the list.