java - java中递归二进制搜索中的lo，hi索引

Question

对于 java 字符串数组(比如 String[] a)的经典二进制搜索，调用搜索方法的正确方法是什么？是吗

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

     }
}

Answer 1

考虑以下情况

a = [ "foo"]

然后您使用 binarySearch(a,key,0,a.length);

搜索关键字“zoo”

代码会在区间[0,1]中搜索，看应该比那个对，下一个递归搜索区间 [1,1]，导致在行

处对 a[1] 进行索引

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

导致数组越界错误。

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