Как реализовать бинарный поиск для массива строк?

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