java - 如何实现字符串数组的二分查找？

Question

我做了一些研究，但找不到任何东西，但如果这是重复的，请告诉我。

我有这个用于整数二分搜索的代码

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

这只是找到并且我理解这个概念。是否可以实现一个在字符串数组中搜索字符串的版本？

我想不出如何实现这个，因为当前的算法检查正在搜索的数字是否高于或低于中间索引，但如果它是一个字符串，我如何检查它是否高于或低于另一个字符串？

我知道我可以使用 String.compareTo() 方法来检查一个字符串是否比另一个字符串更大或更短，但我不确定这是否是实现此目的的正确方法。

Answer 1

如果有两个字符串 s1 和 s2 则

s1.compareTo(s2) 

如果 s1 按字典顺序小于 s2，则返回负结果；如果 s1 按字典顺序大于 s2<，则返回正结果 如果相等则为 0。

所以你可以这样编写你的函数:

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