Solved

Need a Array.BinarySearchStartsWith( String sSearchString ) method

Posted on 2004-04-16
8
281 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…
Visualize your data even better in Access queries. Given a date and a value, this lesson shows how to compare that value with the previous value, calculate the difference, and display a circle if the value is the same, an up triangle if it increased…

623 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