How to implement binary search for array of strings?

Question

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.

Thanks - I'm familiar with that method but I want to implement my own algorithm that does binary search on Strings. I can't see the internal implementation of the method you suggested. — Pablo Gonzalez
– Pablo Gonzalez, Commented May 21, 2016 at 12:42
yes, you can use String.compareTo() method if you want to write your own implementation. — kfx
– kfx, Commented May 21, 2016 at 12:42
Would you have an example of how to use it in such implementation? — Pablo Gonzalez
– Pablo Gonzalez, Commented May 21, 2016 at 12:44
@pgonzaleznetwork the code of the java API is open source. You should be able to look it up under path/to/JDK/src.zip. You can find some examples here, here, here,... — Turing85
– Turing85, Commented May 21, 2016 at 12:44

Keiwan · Accepted Answer · 2016-05-21 12:47:55Z

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);
    }
}

Collectives™ on Stack Overflow

How to implement binary search for array of strings?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related