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”索引中找到的内容。换句话说，我希望返回一个实际的 findAtIndex （该值位于原始数组中的位置），而不是一个布尔值，“已找到/未找到”值。

Answer 1

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

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

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

Answer 2

您不存储递归调用的返回值。将这两行替换

binarySearch(newList, key);

为

foundAtIndex = binarySearch(newList, key);

它应该可以工作。

Answer 3

这是一个返回原始列表中索引的解决方案。主要变化：当您对 binarySearch 进行递归调用时，您将 newList 的偏移量添加到其结果中（与 list 相比）。在midPointValue>中key 这个偏移量为零，因此无需添加任何内容。如果 midPointValue key 则偏移量为 midPoint。

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));
      }
      return 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));
      }
      return midPoint + 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;
}

附加点：

• 在进行下一次递归调用之前无需设置 midPoint。
• 在一个方法内有多个返回是完全合法的。无需一路向下传播结果。
• midPoint 和 midPointValue 中的 point 有点多余。变量名称太长会使代码更难理解。
• 最后，无需创建新列表并将元素从原始列表复制到此新列表。您可以通过添加辅助方法简单地告诉该方法仅检查原始列表的特定部分。

下面是我如何编写这个方法：

public int binarySearch(ArrayList<Integer> list, int key) {
  return binarySearch(list, key, 0, list.size());
}

public int binarySearch(ArrayList<Integer> list, int key, int begin, int end) {

  if(end <= begin) 
    return -1; // Range is empty => key wasn't found

  int mid = (begin + end) / 2;
  int midValue = list.get(mid);

  if(midValue == key) 
    return mid;
  else if(midValue < key) 
    return binarySearch(list, begin, mid);
  else
    return binarySearch(list, mid + 1, end);
}