Efficiency of searching a list

[fam2315]

I need some help with these homework questions.

What is the avg # of nodes accessed in search for a particular element in an unordered list? ordered list? In an unordered array? In an ordered array? Note that a list could be implemented as a linked structure or with an array.

I would think that the number of nodes accessed in an ordered or unordered list would be the same, On, and for an ordered or unordered array would be Ologn

[yellowledbet]

Why do you think that arrays can be searched faster than lists? and why do you think that sorted and unsorted lists can be searched with the same efficiency? same question as previous for arrays?

[fam2315]

I thought both arrays and lists had random access capability (meaning I can get to the ith element at any time), so Im not sure?

[fam2315]

any ideas?

[Junky]

I have plenty of ideas. However in regards to your question it would seem it is your homework and as such you need to provide the answers not just copy and paste what we say, hand it in and get a mark you do not deserve. If you cannot answer these questions then take an F and wait for the teacher to explain the answers. Or you can read your course material and/or search online for discussions on searching. I'm sure Wiki would provide sufficient info on various searching algorithms.

[fam2315]

If you saw my first post, I added what I thought the correct answer was. yellowledbet asked me a question, and I responded, and my response left me with another question. I'm not sure why you feel the need to be so negative. Its a homework question, I have questions about it, and was looking for help on it, that simple. Im also not sure why you think I would 'copy and paste' anything.

[pbrockway2]

First what are you searching for: the value at some given index? or the index of some given value?

I thought both arrays and lists had random access capability (meaning I can get to the ith element at any time),

I am not completely sure of what you are getting at here. But if it relates to accessing the element at a particular index then there are lists and there are lists. (Read the API docs for ArrayList and LinkedList for instance.) As far as I know there are no guarantees made about instances of array: you might guess, but that's not the same thing.

-----

Any questions about how many nodes will be accessed seem to depend on what algorithm you are using.

[Junky]

If you had an unsorted list then how many elements would you have to look at before knowing that the search term was not present? Given 6 1 8 3 9 when would you know 2 is not present.

If you had a sorted list then how many elements would you have to look at before knowing that the search term was not present? Given 1 3 6 8 9 when would you know 2 is not present.

There! Is that better? Was that negative?

[fam2315]

thank you

I see what you are getting at, BUT if I had a list with 1 2 3 4 5, I would only have to search 2 elements to know if 2 was present, and in your example, you had to search the whole list because the element wasn't present.

[Junky]

Yep and your point is?

Surely you can see now the difference in searching a sorted an unsorted list. Whereas in your first post you claimed they would be the same.