CODEWITHSUNDEEP
javaalgorithmbinary-search
Pablo Gonzalez
Pablo Gonzalez

Reputation: 1808

How to implement binary search for array of strings?

I did some research and wasn't able to find anything but if this is a duplicate please let me know.

I have this code for binary search of integers

package thepac;

public class CustomBS{

public static void main(String[] args){
    int[] listOfNumbers = new int[]{2,45,65,76,89,100,342,455};
    int numberToSearch = 100;
    int lowestIndex = 0;
    int highestIndex = listOfNumbers.length-1;
    int middleIndex;

    while(lowestIndex<=highestIndex){
        middleIndex = (lowestIndex+highestIndex)/2;

        if(numberToSearch > listOfNumbers[middleIndex]){
            lowestIndex = middleIndex+1;
        }else if(numberToSearch < listOfNumbers[middleIndex]){
            highestIndex = middleIndex-1;
        }else{
            break;
        }
    }//end of while
    if(lowestIndex > highestIndex){
        System.out.println("not found");
    }else{
        System.out.println("found");
    }
}
}

This works just find and I understand the concept. Is it possible to implement a version of this that searches for Strings as in an array of Strings?

I can't think of how to implement this since the current algorithm checks if the number being searched is higher or lower than the middle index, but if it's a String, how do I check if it's higher or lower than another string?

I know I can use the String.compareTo() method to check if a string is larger or shorter than another one but I'm not sure if this would be the correct way of implementing this.

Upvotes: 2

Views: 2074

Answers (1)

Keiwan
Keiwan

Reputation: 8301

If you have two strings s1 and s2 then 

s1.compareTo(s2)

returns a negative result if s1 is lexicographically smaller than s2, a positive result if s1 is lexicographically bigger than s2 and 0 if they are equal.

So you can write your function like this:

public static void main(String[] args){
    String[] listOfStrings = new String[]{"a","b","c","d","g","h","k","z"};
    String stringToFind = "d";
    int lowestIndex = 0;
    int highestIndex = listOfStrings.length-1;
    int middleIndex = 0;

    while(lowestIndex<=highestIndex){
        middleIndex = (lowestIndex+highestIndex)/2;

        if(stringToFind.compareTo(listOfStrings[middleIndex]) > 0){
            lowestIndex = middleIndex+1;
        }else if(stringToFind.compareTo(listOfStrings[middleIndex]) < 0){
            highestIndex = middleIndex - 1;
        }else{
            break;
        }
    }//end of while
    if(lowestIndex > highestIndex){
        System.out.println("not found");
    }else{
        System.out.println("found at " + middleIndex);
    }
}

Upvotes: 5

Related Questions