Java 在有序字符串数组中进行二进制搜索 ArrayIndexOutOfBoundsException

Question

我正在尝试在 Java 中实现递归二进制搜索算法。

我正在查找有序字符串数组中的字符串。

为什么我在输入“eeeeee”时得到 ArrayIndexOutOfBoundsException，但不是“eeeee”？

提前致谢。

import java.util.Scanner;

class binarySearch{
    public static boolean recursiveBinarySearch(String[] arr, String searchTerm, int start, int end){
        int middle = start + (end-start)/2;
        if(start > end){
            return false;
        }

        if(arr[middle].equals(searchTerm)){
            return true;
        } else if(arr[middle].compareTo(searchTerm) > 0){
            return recursiveBinarySearch(arr, searchTerm, start, middle-1);
        } else if(arr[middle].compareTo(searchTerm) < 0){
            return recursiveBinarySearch(arr, searchTerm, middle+1, end);
        }
        return false;
    }

    public static void main(String[] args){

        Scanner console = new Scanner(System.in);
        String[] saved = {"aaaa","bbbb","cccc","ddddd","eeeee"};
        String searchTerm = "";
        do{
            System.out.println("Term to search in the ordered array:");
            searchTerm = console.nextLine();
        } while(searchTerm.equals(""));
        console.close();
        if(recursiveBinarySearch(saved, searchTerm, 0, saved.length)){
            System.out.println("Term found!");
        } else {
            System.out.println("Term NOT found!");
        }
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

Answer 1

您将 end 作为 saved.length 传递。这里的问题是 .length 会给你从 1 开始计算的长度，而数组使用 0.

只需将 saved.length-1 作为 recursiveBinarySearch 中的 end 传入即可！

import java.util.Scanner;

class binarySearch{
    public static boolean recursiveBinarySearch(String[] arr, String searchTerm, int start, int end){
        int middle = start + (end-start)/2;
        if(start > end){
            return false;
        }

        if(arr[middle].equals(searchTerm)){
            return true;
        } else if(arr[middle].compareTo(searchTerm) > 0){
            return recursiveBinarySearch(arr, searchTerm, start, middle-1);
        } else if(arr[middle].compareTo(searchTerm) < 0){
            return recursiveBinarySearch(arr, searchTerm, middle+1, end);
        }
        return false;
    }

    public static void main(String[] args){

        Scanner console = new Scanner(System.in);
        String[] saved = {"aaaa","bbbb","cccc","ddddd","eeeee"};
        String searchTerm = "";
        do{
            System.out.println("Term to search in the ordered array:");
            searchTerm = console.nextLine();
        } while(searchTerm.equals(""));
        console.close();
        if(recursiveBinarySearch(saved, searchTerm, 0, saved.length-1)){
            System.out.println("Term found!");
        } else {
            System.out.println("Term NOT found!");
        }
    }
}

Answer 2

数组索引从 0 到 4，你传递给它 saved.length，它的值为 5。它不会因“eeeee”而失败，因为代码在到达数组之前找到了数组中的项目错误。将行更改为 saved.length-1.

Java 在有序字符串数组中进行二进制搜索 ArrayIndexOutOfBoundsException

Java binary search in a ordered array of strings ArrayIndexOutOfBoundsException

java

binary-search