implement binary search with string prefix?

You can use default binary search with custom comparator as your base, and then work our range by your self. I think the right algorithm would be:

1. Perform binary search on given array. Use comparator which checks only for prefix.
2. As result you'll get index of string which starts with your prefix
3. Walk to the left to find first string which matches prefix, remember position.
4. Walk to the right to find first string which matches prefix, remember position.
5. Copy elements from range start to range end from original array. That will be your desired array of all elements with prefix match condition.

Below is implementation in java. It works in happy case scenario but will crash if(I left those checks out to make code look simple):

• No strings with given prefix exist in original array
• There are string with length less then prefix length

Also if you need binary search implementation you could check source of Arrays.binarySearch

public class PrefixMatch {

    public static void main(String[] args) {

        final String[] prefixMathces = prefixMatch(new String[] { "Abc", "Abcd", "Qwerty", "Pre1", "Pre2", "Pre3", "Xyz", "Zzz" }, "pre");

        for (int i = 0; i < prefixMathces.length; i++)
            System.out.println(prefixMathces[i]);
    }

    public static String[] prefixMatch(final String[] array, final String prefix) {

        final Comparator<String> PREFIX_COMPARATOR = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.substring(0, prefix.length()).compareToIgnoreCase(o2);
            }
        };

        final int randomIndex = Arrays.binarySearch(array, prefix, PREFIX_COMPARATOR);

        int rangeStarts = randomIndex, rangeEnds = randomIndex;

        while (rangeStarts > -1 && array[rangeStarts].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeStarts--;

        while (rangeEnds < array.length && array[rangeEnds].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeEnds++;

        return Arrays.copyOfRange(array, rangeStarts + 1, rangeEnds);
    }
}

I assume that you currently have something like this? :

arrayElement.compareTo(prefix)

If so, you can change it to look like this:

arrayElement.startsWith(prefix) ? 0 : arrayElement.compareTo(prefix)

I suggest looking into the API code for this. There is an Arrays class that you can check out in the java.lang package and learn from there.

Working on a similar problem right now. I believe pseudo code will go something like yours. I created a pojo class Song. A song is made up up three strings artist,title, and lyrics.

When you create a song object you get :

     //     Artist             Title                     Lyrics..

Song a = ["Farmer Brown", "Oh' Mcdonalad", "Oh'mcdonal had a farm eh i oh i oh"]

public class Song implements Comparable<Song> {

private String _artist;  
private String _lyrics;
private String _title;

   // constructor
   public Song(String artist, String title, String lyrics) {
   this._artist = artist;
   this._title = title;
   this._lyrics = lyrics;
   }

   public String getArtist() {
       return _artist;
   }

   public String getLyrics() {
       return _lyrics;
   }

   public String getTitle() {
       return _title;
   }

   public String toString() {
       String s = _artist + ", \"" + _title + "\"";
    return s;
   }

   //This compare two song objects
   public int compareTo(Song song) {
       String currentSong = song.toString();
       int x = currentSong.compareToIgnoreCase(this.toString());  
       return x;
   }

This is your method here that will take in the array of songs and your prefix and use the compare method to see if they match. If they match the compareTo method returns a 0. If you get a 0 then you know you have found your song so return the arrayOfSongs[index where song is found].

I have not coded up my search yet but I modified yours to match my code. I have not tested it yet. I don't think you even need a compareTo method but you can use it. Also for scaling the binary search should return a list of songs that might match as you might have multiple songs that start with "xyz" . Kind of when you start searching on google with prefix "do" you get a drop down of "dog, donut,double" which gives the user something to choose like a search engine.

    public static ArrayList<Song> search (String[] arrayOfSongs , String enteredPrefix) {
     ArrayList<Song> listOfMatches = new ArrayList<Song>;
     int mid;
     int lo = 0;
     int hi = arrayOfSongs.length - 1;
     while(lo <= hi) 
     {
     mid = (hi + lo) / 2;
       if(arrayOfSongs[mid].startsWith(enteredPrefix))
       {
         System.out.println("Found a match, adding to list");
         listOfMatches.add(arrayOfSongs[mid]);
       }    
    }   
    return listOfMatches;
}

Once you have a listOfMatches of possible suspects of the song you want you can use the compareTo method in some way.