Solved

Need a Array.BinarySearchStartsWith( String sSearchString ) method

Posted on 2004-04-16
8
280 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
Revamp Your Training Process

Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action.

 
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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Summary: Persistence is the capability of an application to store the state of objects and recover it when necessary. This article compares the two common types of serialization in aspects of data access, readability, and runtime cost. A ready-to…
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.
This video shows how to use Hyena, from SystemTools Software, to update 100 user accounts from an external text file. View in 1080p for best video quality.

751 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