We help IT Professionals succeed at work.

Check out our new AWS podcast with Certified Expert, Phil Phillips! Listen to "How to Execute a Seamless AWS Migration" on EE or on your favorite podcast platform. Listen Now

x

Trying to find an element in a string array

aztec
aztec asked
on
Medium Priority
141 Views
Last Modified: 2010-04-04
Hi...
  I need to be able to search for a string in a string array of 250 different constants. Basically I read a line from a file,  then go thru a for loop 250 times checking against each element of the array to see if the line matches one of the strings in there. Then I read in the next line from the file and do the whole process again. This takes a really long time for it to run. Is there a quicker, more efficient way?

thanks,
   Shawn Halfpenny
   drumme59@sprint.ca
Comment
Watch Question

Commented:
Hi,

I am happy that somebody up there(my local time is 9:28 p.m). And the answer is YES. We can make the complexity of your search in the order of O(log2(N)) with binary search as follows:
- Insert all your 250 strings to a TStringList and set sorted property to true
- Read aline from file and use( say you have StList)
  if StList.Find(MyCnstReadFromFile, Index) then
  begin
     // you have found it at Index'th item in the list
  end;

Regards, (need full source, just give me couple of examples about your constants but it may say several minutes)
Igor

Commented:
inter,

does TStringlist uses smart search?

Zif.

Commented:
Let me see...here in few moments...(I suppose binarry search is embeded)

Commented:
Yes, It sorts with quicksort and searches with binary search. It is fast, so lets calculate,

if the set has 250 elements one should search all in normal search which has
250 ops
binary search does it in
log2(250) = log10(250)/log10(2)=7.97 => 8 ops
so there is about 250/8 = 31.25 speed up.
So in plain if it does in 100 secs
in fast mode it does it in 3.2 secs (theoretically)
Regards,
Igor

Commented:
well Igor, you did it again.

Author

Commented:
Indeed, as Zifnab put it Igor, you have done it again! Works great and very fast too! Give yourself an 'A' on this one.

Thanks
   Shawn Halfpenny
If your array is sorted then you could do a Btrieve style search.  Your value is either < or > the value of the current element.  Temp[0] < Value then jump half way.  If Temp[125] > Value then jump back half way.  If Temp[75] < Value ... and so on.
If you don't require an array, you could use a TStringList which gives you two easy methods.  TStringList.IndexOf() or TStringList.Find().

D.

Commented:
Hi, thanks,
Am I supposed to post an answer?
Commented:
Unlock this solution with a free trial preview.
(No credit card required)
Get Preview
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a free trial preview!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.