Results 1 to 13 of 13
Thread: Efficiency of Searching
 08032011, 02:18 AM #1Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
Efficiency of Searching
I am taking a data structures course, and could use a little help with the concept of searching efficiency. So far, we have studied how having an indexed array can be used when searching a file, but one of the questions is confusing me. It asks:
Compare the efficiency of searching an ordered sequential table of size b and searching an unordered table of the same size for the key key:
 If no record with 'key key' is present
I have not been able to get in contact with the instructor, but im guessing 'key key' is not a typo. Can someone help clarify what this is asking? I would guess that its saying if we have 2 tables, one ordered, and one unordered, is the searching efficiency effected by having a 'key key'. I'm just a little confused, any help would be greatly appreciated.
 08032011, 02:21 AM #2
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
How would you search something that's unordered manually? Would you check each element, or check random elements? How would you find page x in some book? Would you use any sort of method to get there as quickly as possible? Or would you check each page to see if it is page x? Looking up linear search, and binary search will be helpful as well.
 08032011, 02:30 AM #3Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
If its unordered and no 'key key', I would guess that you would try to do it almost like a dictionary search, where you grab a handful of 'pages' and if you go too far, back up, if you pass it, go forward, etc, but I'm not sure how to articulate that. Im guessing were comparing the big oh notation for the efficiency, so with no key key for an unordered table it would be O(n^2).
Last edited by fam2315; 08032011 at 02:32 AM.
 08032011, 02:34 AM #4
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
If you are given an unordered dictionary, how would you know if you've gone past the key? Unordered implies not in alphabetic order. So you could have the word Apple, followed by Zebra, followed by Orange. So what would you do to find some randomly given word? Would you be able to devise any 'smart' approach? Or would you have to use a brute force approach?
Now an ordered dictionary may have a different approach. Since you know for a fact that Apple comes before orange, and orange comes before zebra, you can think up a 'smart' approach.
 08032011, 02:36 AM #5Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
I see,
So for an unordered table, since there is no key for the file, we would have to perform n searches to find the record we want, where n is the number of records, so its a linear search.
If it is ordered, I think the average was n/2 comparisons.
I guess i'm more confused because when we talk about searching a 'table' I don't know what data structure in java that would be. A 2d array?Last edited by fam2315; 08032011 at 02:40 AM.
 08032011, 02:42 AM #6
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
You are right on the unordered list, it will be O(n), but I don't believe you are correct on the next part. When you search a dictionary, and think like a computer, you don't know that if you are looking for a z word to start near the back, a computer would start at exactly halfway. You would test the page exactly halfway through the dictionary and either three things can happen. The word can be on the halfway page, the word can be less than the halfway page, or it will be past the halfway page. You can repeat this successive halving and checking approach and guarantee that you will eventually find the key(if it exists).
 08032011, 02:49 AM #7Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
For ordered lists, once we go beyond the point where the item should be, we can stop, because (assuming the data is ordered), the key is not there. So after we perform k searches, and k is greater or lower (depending on the order of data, ascending or descending), we know the key is not present in the list.
Last edited by fam2315; 08032011 at 02:54 AM.
 08032011, 02:54 AM #8
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
Not so in an ordered list. If you have a dictionary, let's say the halfway word happens to be Mango, and the key is zebra(and let's say this dictionary doesn't know what a zebra is), would you ever be checking any page before Mango? Is it possible that a word that starts with a Z can ever be found in the A section, or b, c, d,... ?
Try this, take an ordered list of 1100, and don't specify a key, but write on paper the successive halfs. I'll even start you out:
100>50>75>...
Finish this, at each halfway point you can choose whether you want to go up or down, but this will eventually terminate. Once it does terminate, count how many steps you took and see how quickly(or slowly) it terminated and use this to try to hypothesize what the big o notation will be.
 08032011, 04:29 AM #9Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
I have one more question:
Suppose you have a file of data of approximately 10,000 personnel records using Social Security numbers as primary key. You have decided to store the file as an indexed sequential structure.
How should the index be accessed?
What is meant by accessing the index?
 08032011, 04:36 AM #10
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
What kind of data structure do you think should be used? Do you know of any data structures that can be indexed into? Which ones are sequential?(meaning to find the nth item you must first check the 1st, 2nd,...,n1,nth)
 08032011, 04:39 AM #11Member
 Join Date
 Feb 2011
 Posts
 78
 Rep Power
 0
a LinkedList is sequential but an array can be indexed.
 08032011, 06:20 AM #12
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
Check the linked list API to see if it has any methods to get index i.
 08032011, 09:44 AM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,679
 Blog Entries
 7
 Rep Power
 21
Does the term 'sequential' imply that you can only traverse the table one record by one record? Or can you hop through the table at will? If it is the first an ordered table takes b/2 steps on average, an unordered table takes b steps. If you can hop through the table(s) randomly an ordererd table takes 2log(b) steps to conclude that a record is not in the table.
kind regards,
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

Efficiency of searching a list
By fam2315 in forum New To JavaReplies: 9Last Post: 06292011, 04:34 AM 
Cryptography Efficiency
By joshdgreen in forum Advanced JavaReplies: 22Last Post: 10292010, 10:16 AM 
URLConnection Efficiency
By Lil_Aziz1 in forum New To JavaReplies: 22Last Post: 08192010, 07:27 PM 
An Efficiency Question
By Revenna in forum Java 2DReplies: 0Last Post: 06252010, 08:22 AM 
method efficiency
By TheWave in forum Advanced JavaReplies: 0Last Post: 02132008, 05:11 AM
Bookmarks