Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Modified Binary Search

by bobf (Monsignor)
on Jan 13, 2010 at 18:09 UTC ( #817245=note: print w/ replies, xml ) Need Help??


in reply to Modified Binary Search

If you looking for feedback on your proposed algorithm (rather than code)...

I would probably take a similar approach, assuming that the array is large enough that a binary search is expected to be more efficient than creating an index of the first n characters of each string.

Keep in mind, though, that when you do the binary search for $beg you are getting information not only about the position of $beg, but also about $end. Each time you compare a string from the array to $beg you could also determine the relative location of $end to that string. Then, once you nail down the position of $beg you could potentially start searching for the exact position of $end using a much smaller search space. (The actual benefit achieved will depend on the positions of $beg and $end within the array.)


Comment on Re: Modified Binary Search
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://817245]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (13)
As of 2015-07-02 09:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (33 votes), past polls