Results 1 to 10 of 10
Like Tree1Likes
  • 1 Post By Junky

Thread: Efficiency of searching a list

  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default Efficiency of searching a list

    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

  2. #2
    yellowledbet is offline Senior Member
    Join Date
    Feb 2011
    Location
    Georgia, USA
    Posts
    122
    Rep Power
    0

    Default

    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?

  3. #3
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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?

  4. #4
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    any ideas?

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    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.

  6. #6
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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.

  7. #7
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,574
    Rep Power
    12

    Default

    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.

  8. #8
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    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?
    sunde887 likes this.

  9. #9
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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.

  10. #10
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    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.

Similar Threads

  1. what code for searching in drop down list?
    By Harmesh Goyal in forum Advanced Java
    Replies: 1
    Last Post: 03-03-2011, 05:43 AM
  2. URLConnection Efficiency
    By Lil_Aziz1 in forum New To Java
    Replies: 22
    Last Post: 08-19-2010, 07:27 PM
  3. An Efficiency Question
    By Revenna in forum Java 2D
    Replies: 0
    Last Post: 06-25-2010, 08:22 AM
  4. Searching for a String within an linked list
    By phil128 in forum Advanced Java
    Replies: 5
    Last Post: 04-13-2009, 03:18 AM
  5. Searching through a list.
    By wethekings in forum New To Java
    Replies: 3
    Last Post: 02-24-2009, 01:43 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •