Ah - I see - very good, thanks! But you also need to employ some logic at looking at the characters in the string - first the first letter, then once you get down to a list where they all have the same first letter, then take the second, and so forth until you only have one item left - sounds complicated.
Reason this whole thing got started with me was Grant Skinner's presentation on AS3 optimization http://www.gskinner.com/talks/quickNL/ See slides 68 & 69. Binary way faster than linear searching - but no examples on implementing it. I can see how to write this now - but wonder if it would be worth it if using Dictionary would be faster - anyone know? Jason Merrill Bank of America Global Learning Learning & Performance Solutions Join the Bank of America Flash Platform Community and visit our Instructional Technology Design Blog (note: these are for Bank of America employees only) -----Original Message----- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Hans Wichman Sent: Thursday, May 06, 2010 11:06 AM To: Flash Coders List Subject: Re: [Flashcoders] Doing a binary search in AS3? the most important thing being as Hendrik said that it is sorted, which in your example it is not. Say you have: ["apple", "banana", "cherry", "kiwi", "orange", "peach" "pear", "pineapple", ] and you are looking for banana: middle element is orange (or kiwi) take "apple", "banana", "cherry", "kiwi", middle element is cherry take "apple", "banana" middle element is banana yeah a hit My description is a bit shabby but you get the idea. Whether it beats a dictionary ... I don't think so, I've only done this when searching through huge sorted files with random file access, not with arrays in flash. regards Hans On Thu, May 6, 2010 at 4:44 PM, Henrik Andersson <he...@henke37.cjb.net>wrote: > Merrill, Jason wrote: > >> I understand what a binary search algorithm is, but am wondering how >> that could be implemented on an array in Actionscript (if at all) >> without using methods that would defeating the purpose of a binary >> search (speed). Anyone have experience in this area? >> >> So for example, if you have a list like this: >> >> ["apple", "orange", "banana", "pear", "cherry", "pineapple", "kiwi", >> "peach"] >> >> Then to do a binary search for say, "pineapple", as I understand >> binary searching, you would first split the list in the middle (between "pear" >> and "cherry") and determine if "pineapple" was in that list - if not, >> search the other half and so on until you find "pineapple". >> > > That is wrong, you know that it will be in a certain half due to the > list being sorted. There is no need to scan the half for the object, > by the list already being sorted, you know that if the object exists, it's in that half. > Just compare the middle element, if it is bigger, use the left half, > else use the right half. > > _______________________________________________ > Flashcoders mailing list > Flashcoders@chattyfig.figleaf.com > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
