java - BinarySearch 在列表中找不到元素，即使它存在 : Java

Question

谁能指出我这里哪里出错了？我用调试器逐步检查它，看起来我的算法应该找到搜索键，但事实并非如此。 (为了检查，我打印出“在索引处找到”，然后打印出 [已排序] 列表的内容；我搜索的元素 123 在列表中，但返回的“未找到”值为 -1。)

public int binarySearch(ArrayList<Integer> list, int key){
    int foundAtIndex  = -1;
    int midPoint = list.size()/2;
    int midPointValue = list.get(midPoint);

    if(list.size() > 1){
        if(midPointValue == key){
            foundAtIndex = midPoint;
        }
        else if(midPointValue > key){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int i = 0; i < midPoint; i++){
                newList.add(list.get(i));
            }
            midPoint = midPoint / 2;
            binarySearch(newList, key);
        }
        else if(midPointValue < key){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int j = midPoint+1; j < list.size(); j++){
                newList.add(list.get(j));
            }
            midPoint = midPoint / 2;
            binarySearch(newList, key);
        }
    }
    else if(list.size() == 1){
        if(list.get(0) == key){
            foundAtIndex = 0;
        }
    }

    //return the index where the key was found, or -1 if not found
    return foundAtIndex;
}

编辑:好的，现在它找到了，但我的问题是我需要返回它在原始 数组中找到的索引。实际上，它缩小范围然后返回“newList”中元素的索引。所以它总是会返回它，因为它是在 'newList' 的索引中找到的。换句话说，我希望返回一个实际的 foundAtIndex(值在原始数组中的位置)，而不是 boolean 值，“未找到/未找到”值。

Answer 1

每次调用 binarySearch(newList, key); 都会丢失返回结果。

您需要设置foundIndex = binarySearch(newList,key)。

此外，因为您依赖于 list.size() 作为中点 - 您将需要调整返回结果(否则它将始终为 -1 或 0)。