Archived

This topic is now archived and is closed to further replies.

Last Attacker

SegSeqSearch

Recommended Posts

I'm posting this after I've read the other guy's sorting algo post... Just the other day, (just for fun) I draw an array of elements (about 15 elements) on paper and implemented the linear search algorythm. Ok, I know it goes from 1 element to the other but I thought by myself, that there has to be a faster searching algo for UNSORTED arrays. So I sat and tried to think of something... I later realised that I cannot exclude any element from the array, but I wondered if I could have a better propability search, you know, search the areas of the array that is more likely to have the element first, and so on. I came onto this algo I've developed... I call it SegSeqSearch (Segment Sequential Search). It has that same worst case as linear-search but I hope it has a better average case than linear. Here's how it works : * It checks the first, middle and last element * Then moving from the middle to the left, it checks a 1/4 of those elements * Then it moves from the middle to the right and checks a 1/4 of those elements * It moves from the last element to the left checking a 1/4 of those elements * Then it checks the first 1/4 elements from the first element. The bottom 3 checks are performed excluding the first, middle and last element ofcource. I performed a profile check and if the searched element is in the middle of the array, it'll be found MUCH quicker than linear search, you can check this out for yourself, my algo checks about 75% of an array before linear even gets there. What do you guys think? I guess there must be an faster searching algo out there (for unsorted arrays), if you guys know of one, please tell me! // Last Attacker \\---=( LA )=---// LA Extreme \\

ICQ Number : 120585863

E-mail: laextr@icqmail.com [edited by - Last Attacker on May 25, 2004 10:03:41 AM]

Share this post


Link to post
Share on other sites
It will take the same amount of time on average. It''s equivalent to magically reordering the list in the indicated fashion in zero time, and then linearly searching the reordered list.

It simply is not possible to do better on unsorted data*. The problem is that at any point in the search (before success), the actual element could *always* be *any* element not already looked at. The reason that sorting the data helps is that you can then gain information from looking at a "wrong" element ("well, if it''s not this element, then it can''t be in this part of the list either").

* Unless you have statistical data indicating that certain elements are requested more often; you can then put those near the beginning of the list.

Share this post


Link to post
Share on other sites
Well, you can insert a parameter to search a 1/4 of the array first, if you think that the element you''re looking for lies in that area.

Yeah, it can take the same amount of time to search a whole array as linear but, whats the chance for an element you''re looking for to be in the first 1/4 of the array? I know it can end up there, but I guess there could be some modifications made to the algo for best results.

I have tested my algo with linear search a couple of times trying to search an element in an array of 1000 elements while running a profiler ... mine had a better average (MUCH better).
The profiler showed that the linear search took like 23.###% of the time while mine took 1.###% of the time.
But mine can take the longest if the element you''re looking for lies in the first 1/4 of the array.

// Last Attacker \\---=( LA )=---// LA Extreme \\

ICQ Number : 120585863

E-mail: laextr@icqmail.com

Share this post


Link to post
Share on other sites