Solved

Need a Array.BinarySearchStartsWith( String sSearchString ) method

Posted on 2004-04-16
8
273 Views
Last Modified: 2010-04-15
Hi there, i am looking for a way to do a binary search over an array based on a input string. This is different from other BinarySearch algos because i need to check the StartsWith which will be a superset of the normal BinarySearch.

For example, for an array with elements  { "hello", "dude" } , even an input string of "he" or "hell" or "dud" or "dude" will return a true because i check for StartsWith on the string array and not the entire string in question. I think the question is clear enough.

I need a solution for this which does not iterate over the entire array but uses binarysearch mechanisms or some other algo which will figure out a way to find the element in the shortest possible walking of the tree.

Any help is welcome !
0
Comment
Question by:kuzco
  • 4
  • 3
8 Comments
 
LVL 22

Expert Comment

by:_TAD_
ID: 10842449


One question...

Let's suppose you have the list

apple
horse
hello
zebra

And you do a binary search for h*

Did you just want the first value it finds (horse), or did you want all matching values (horse, hello)?
0
 
LVL 5

Author Comment

by:kuzco
ID: 10842978
Good question ! I would expect all matching values for the search of h*. Although at the moment i'm not using regex kind of wildcard matching, i plan to do so in the future.

Basically, it would be simpler if you return both horse and hello because it would mean that it is the binary mean of the n-1 th set. So while doing the binary search, say you reached horse first, then you can find if there are some more h* values above it (apple) and return that too ... Hope this is not very confusing !

TAD, Yes i want all the matching params.
0
 
LVL 11

Expert Comment

by:Agarici
ID: 10844235
suggestion:
do a binary search with a custom comparer until you find one match (lets say match at index i i the array ) and then search up and down from that index until you have no match. the custom comparer may implement any kind of comparison you wish

something like:
iMatch = Array.BinarySearch( YourArray,0,YourAray.Length, SearchedValue, YourCustomComparer)
if( iMatch >= 0 )
{
// YourSolArray is the array of matched indexes
YourSolArray.Add( iMatch )

//search up
i = iMatch
while( i < YourArray.Length && YourCustomComparer.Compare( SearchedValue, YourArray[i] )
{
YourSolArray.Add( i )
i++
}
//search down
i = iMatch
while( i >= 0 && YourCustomComparer.Compare( SearchedValue, YourArray[i] )
{
YourSolArray.Add( i )
i--
}

}



hth.

A.
0
 
LVL 5

Author Comment

by:kuzco
ID: 10848723
hey you forget that i need only StartsWith and not the entire string to exist in the array. Your BinarySearch call will only return an index if and only if an exact match does exist in the Array. Or else it shall return -1 ... So this is not what i want ..

I've already tried something like this but the whole point is that the Array.BinarySearch has to be replaced with a Array.BinarySearchStartsWith method.
0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 11

Expert Comment

by:Agarici
ID: 10848729
only the comparer has to be replaced
0
 
LVL 5

Author Comment

by:kuzco
ID: 10848793
hmm ... ok ! i get the picture but trying to implement that, i got kicked in the head.

Any code sample for the comparer would help !
0
 
LVL 11

Accepted Solution

by:
Agarici earned 125 total points
ID: 10848829
// example of a comparer that uses only first 3 chars from a string
class MyTypeNameComparer: IComparer
  {
    public int Compare (object x, object y)
    {
        string tempObj1 = (string)x;
        string tempObj2 = (string)y;
       
        return x.Substring(0,3).CompareTo (tempObj2.substring(0,3));
    }
0
 
LVL 5

Author Comment

by:kuzco
ID: 10848907
duh ! that was simple ... i was thinking maybe you gotta implement the whole BinarySearch algo and replace the equality mechanism with StartsWith mechanism or something like that ... ugh ... i hate myself !

Thanks for the help dude ...
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Introduction                                                 Was the var keyword really only brought out to shorten your syntax? Or have the VB language guys got their way in C#? What type of variable is it? All will be revealed.   Also called…
Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now