Java:递归二进制搜索以查找阵列逻辑错误的元素

Question

我正在尝试使用二进制搜索回复在数组中找到一个元素。我无法弄清程序中的逻辑有什么问题，因为我会遇到不正确的输出。说如果我搜索5，我将获得的输出为4。同样，我也无法在其他情况下获得正确的结果。该程序可能有什么问题？

public class OrdArray {
    private long[] a;
    private int nELems;

    public OrdArray(int max){

    a=new long[max];
        int nElems=0;
    }
    public int size(){
        return nELems;
    }
    public void insert(int value){
        int j;
        for(j=0;j<nELems;j++){
            if(a[j]>value){
                break;
            }
        }
        for(int k=nELems;k>j;k--){
            a[k]=a[k-1];
        }
        a[j]=value;
        nELems++;
    }
    public void display(){
        for(int i=0;i<nELems;i++)
        System.out.print(a[i]+" ");
        System.out.println(" ");
    }
    public int Recursionfind(int low,int high,int key){
        if(low>=high){
            return nELems;
        }
        int mid=(low+high)/2;
        if(a[mid]== key){
            return mid;
        }
        if(a[mid]>key){
            return Recursionfind(low,mid-1,key);
        }
        else{
            return Recursionfind(mid+1,high,key);
        }
    }
}

class OrderedApp{
    public static void main(String[] args) {
        int maxsize=100;
        OrdArray arr;
        arr=new OrdArray(maxsize);
        System.out.println("Insert array:");
        arr.insert(3);
        arr.insert(5);
        arr.insert(1);
        arr.insert(7);
        arr.insert(6);
        arr.insert(4);
        arr.insert(8);
        arr.insert(2);
        arr.insert(9);
        arr.display();
        int n=arr.size();
        System.out.println(n);
        int key=5;
        System.out.println("Key is :" + arr.Recursionfind(0,n-1,key));
    }
}

Answer 1

此错误位于这里：

if(a[mid]== key){
    return mid;
}

您将搜索值与位置mid的数组值匹配。如果您发现它必须返回找到的值而不是键。

if(a[mid]== key){
    return a[mid];
}

您还必须将a从long[]更改为int[]。