java - 使用字符串的通用二分搜索

Question

我有一个通用的二分搜索，它可以正确搜索 Array 中的Integers。但是，当应用于 Strings 的 Array 时，它最多只能正确返回三个索引 ([1],[2],[3])，同时标记其他的视为不存在 ([-1])。预先感谢您的任何见解。

public class BinarySearch {

private BinarySearch() { }

private static <T extends Comparable<? super T>> int search(T[] list, int first, int last, T key){
    int foundPosition;
    int mid = first + (last - first) / 2;  
    if (first > last)
        foundPosition = -1;
    else if (key.equals(list[mid]))
        foundPosition = mid;
    else if (key.compareTo(list[mid]) < 0)
        foundPosition = search(list, first, mid - 1, key);
    else
        foundPosition = search(list, mid + 1, last, key);
    return foundPosition;
} 

public static void main(String args[]) {
    //Integer
    Integer [] searchInteger = {0,2,4,6,8,10,12,14,16};
    int integerLast = searchInteger.length-1;
    System.out.println("Integer test array contains...");
        for (Integer a1 : searchInteger) {
         System.out.print(a1 + " ");
        }
    System.out.println("\nChecking Integer array...");
    int result;
    for (int key = -4; key < 18; key++) {
        result = BinarySearch.search(searchInteger, 0, integerLast, key);
        if (result < 0)
            System.out.println(key + " is not in the array.");
        else
            System.out.println(key + " is at index " + result + ".");
        }
    //String
    String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"};      
    System.out.println("String test array contains...");
    for (String a1 : searchFruits) {
        System.out.print(a1 + " ");
    }
    System.out.println("\nChecking String array...");
    int results;
    int fruitLast = searchFruits.length-1;
    for (int key = 0; key < searchFruits.length; key++){
        results = BinarySearch.search(searchFruits, 0, fruitLast, searchFruits[key]);
        System.out.println("Key = " + searchFruits[key]);
        System.out.println("Index result = " + results);
        if (results < 0)
            System.out.println(searchFruits[key] + " is not in the array.");
        else
            System.out.println(searchFruits[key] + " is at index " + results + ".");        
    }
}
}

Answer 1

因为你的字符串数组

    String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"}; 

未排序，与您的整数数组相同

  Integer [] searchInteger = {0,2,4,6,8,10,12,14,16};

已排序。

顺便说一下，你可以使用 Arrays.binarySearch()也是。