Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Need a Array.BinarySearchStartsWith( String sSearchString ) method

Posted on 2004-04-16
8
Medium Priority
?
283 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say 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

Extention Methods in C# 3.0 by Ivo Stoykov C# 3.0 offers extension methods. They allow extending existing classes without changing the class's source code or relying on inheritance. These are static methods invoked as instance method. This…
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…
In this video you will find out how to export Office 365 mailboxes using the built in eDiscovery tool. Bear in mind that although this method might be useful in some cases, using PST files as Office 365 backup is troublesome in a long run (more on t…
Have you created a query with information for a calendar? ... and then, abra-cadabra, the calendar is done?! I am going to show you how to make that happen. Visualize your data!  ... really see it To use the code to create a calendar from a q…
Suggested Courses

705 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