Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Need a Array.BinarySearchStartsWith( String sSearchString ) method

Posted on 2004-04-16
8
Medium Priority
?
285 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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
 
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 500 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

Ask an Anonymous Question!

Don't feel intimidated by what you don't know. Ask your question anonymously. It's easy! Learn more and upgrade.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Although it is an old technology, serial ports are still being used by many hardware manufacturers. If you develop applications in C#, Microsoft .NET framework has SerialPort class to communicate with the serial ports.  I needed to…
Hello there! As a developer I have modified and refactored the unit tests which was written by fellow developers in the past. On the course, I have gone through various misconceptions and technical challenges when it comes to implementation. I would…
This video shows how to quickly and easily deploy an email signature for all users in Office 365 and prevent it from being added to replies and forwards. (the resulting signature is applied on the server level in Exchange Online) The email signat…
Despite its rising prevalence in the business world, "the cloud" is still misunderstood. Some companies still believe common misconceptions about lack of security in cloud solutions and many misuses of cloud storage options still occur every day. …
Suggested Courses
Course of the Month12 days, 10 hours left to enroll

971 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