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

РЕДАКТИРОВАТЬ: Хорошо, теперь он находит это, но моя проблема в том, что мне нужно вернуть индекс, в котором он был найден в массиве original .Как это, он сужает его, а затем возвращает индекс элемента в 'newList'.Таким образом, он всегда будет возвращать его как найденный в индексе в терминах 'newList'.Другими словами, я хочу вернуть фактическое значение foundAtIndex (в каком положении находится значение в исходном массиве), а не логическое значение «был / не найден».

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 перед следующим рекурсивным вызовом.
• Совершенно законно иметь несколько возвратов внутри метода. Нет необходимости распространять результат до конца.
• point в midPoint и midPointValue является излишним. Слишком длинные имена переменных затрудняют понимание кода.
• Наконец, нет необходимости создавать новый список и копировать элементы из исходного списка в этот новый список. Вы можете просто сказать методу, чтобы он проверял только определенную часть исходного списка, добавив вспомогательный метод.

Вот как бы я написал этот метод:

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