通用二进制搜索使用连续字符的键失败

Question

我有一个通用的二进制搜索，它似乎与 Integers 一起运行良好。但是，当我尝试将它与 Strings 一起使用时，它有时会崩溃，在多行显示 ArrayIndexOutOfBoundsException；特别是我多次使用同一个字母指定一个单词的键。例如String key = "peach";returns正确的索引，String key = "blueberry";没有找到，String key = "scoop";导致失败。它似乎与 T 中的 (key.equals(list[mid])) 有关，但我无法理解。感谢您的帮助。

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 [] a = {0,2,4,6,8,10,12,14,16};
int finalIndex = 9;
System.out.println("Integer test array contains...");
    for (Integer a1 : a) {
        System.out.print(a1 + " ");
    }
int result;
for (int key = -4; key < 11; key++) {
    result = BinarySearch.search(a, 0, finalIndex, key);
    if (result < 0)
        System.out.println("\n" + key + " is not in the array.");
    else
        System.out.println("\n" + key + " is at index " + result + ".");
}

String[] searchFruits = {"lemon", "apple", "banana", "peach", "pineapple", "grapes", "blueberry", "papaya"};   
System.out.println("\nChecking fruits...");
System.out.println("String test array contains...");
 for (String a1 : searchFruits) {
        System.out.print(a1 + " ");
    }
int fruit = 8;
int fresult;
String key = "blueberry";
    fresult = BinarySearch.search(searchFruits, 0, fruit, key);
    if (fresult < 0)
        System.out.println("\n" + key + " is not in the array.");
    else
        System.out.println("\n" + key + " is at index " + fresult + ".");
}

}

Answer 1

所以问题是您使用数组的大小作为索引，导致数组索引越界问题。

具体

int finalIndex = 9;

和

int fruit = 8;

现在，您有时只能看到异常的原因取决于二进制搜索的方式。如果您要搜索的值小于中间值，它将沿着索引的下半部分向下移动，从而达到零并且永远不会抛出索引越界异常。但是，如果该值大于中间值，您将递增直到您达到最后一个值，在本例中为“8”，这将给出一个超出范围的索引。

您需要将索引值减一以说明从 0 开始的索引。

示例：

int finalIndex = a.length-1;

int fruit = searchFruits.length-1;

通用二进制搜索使用连续字符的键失败

Generic Binary Search Fails Using A Key Of Consecutive Characters

java

arrays

generics

binary-search

compareto