1

对于 java 字符串数组（例如String[] a）上的经典 binarySearch，调用搜索方法的正确方法是什么？是吗

binarySearch(a,key,0,a.length)

或者

binarySearch(a,key,0,a.length-1)

我为下面的实现尝试了两种方法，并且似乎都有效.. 是否存在这些调用中的任何一个都可能失败的用例？

class BS{
    public static int binarySearch(String[] a,String key){
        return binarySearch(a,key,0,a.length);
        //return binarySearch(a,key,0,a.length-1);
    }
    public static int binarySearch(String[] a,String key,int lo,int hi)   {
        if(lo > hi){
            return -1;
        }
        int mid = lo + (hi - lo)/2;
        if(less(key,a[mid])){
            return binarySearch(a,key,lo,mid-1);
        }
        else if(less(a[mid],key)){
            return binarySearch(a,key,mid+1,hi);
        }
        else{
            return mid;
        }

    }
    private static boolean less(String x,String y){
        return x.compareTo(y) < 0;
    }
     public static void main(String[] args) {
        String[] a = {"D","E","F","M","K","I"};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
        int x =  binarySearch(a,"M");
        System.out.println("found at :"+x);

     }
}
4

2 回答 2

1

考虑以下情况

a = [“富”]

然后你搜索关键字“zoo”binarySearch(a,key,0,a.length);

代码将在区间[0,1]中搜索它，看到它应该比那个正确，下一个递归搜索区间[1,1]，导致a[1]在行的索引

if(less(key,a[mid])){

导致数组越界错误。

第二种解决方案可以正常工作。

于 2013-08-26T05:47:16.647 回答
1

我认为第二种方法是安全的。

考虑这种情况 - 您有一个包含 9 个元素的数组，并且键位于最后一个索引（第 8 个元素）。如果您遵循第一种方法，那么您可能会有这样的方法调用 -

binarySearch(a, key, 9, 9);

现在，在该方法执行中，下一行中的整数除法将得到 9 -

int mid = 9 + (9 - 9)/2;

你将在下一行用 9 索引你的数组 -

if( less(key,a[mid]) ) { // You'll face ArrayIndexOutOfBoundException
    ....
}

这将是无效的并导致ArrayIndexOutOfBoundException.

然而，第二种方法会很好。

于 2013-08-26T05:39:50.103 回答