Hi Jason, the complexity probably isnt that hard. You have s, you look at wordlist[wordlist.length/2], you find a g, so clearly you have to repeat that for the upper half of the list etc. Dictionary is not going to work here at least not on the whole words, you would have to store partial lookups eg dictionary["a"] -> all words starting with a here, etc. Maybe even nested dictionaries.
regards, JC On Thu, May 6, 2010 at 5:19 PM, Merrill, Jason < jason.merr...@bankofamerica.com> wrote: > 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 > _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
