Мой базовый метод двоичного поиска не работает для одного определенного значения в массиве int в Java

Question

Я начинающий java ученик, и вот небольшая программа, которая выводит индекс искомого значения int в массиве int. Вот код

public static void main(String[] args) { 

    int rank =findNumber(7, new int[]{2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79}); 
    System.out.println("Your number's index is " + rank); 

} 

public static int findNumber(int key, int... numbers) { 
    int low = 0; 
    int high = numbers.length - 1; 
    int mid = (low + high)/2; 
    int rank = 0; 
    for (int i = low; i < high; i++) { 
     if (key < numbers[mid]) { 
      high = mid; 
      mid = (low + high)/2; 
     } else if (key > numbers[mid]) { 
      low = mid; 
      mid = (low + high)/2; 
     } else { 
      rank = mid; 
      return rank; 
     } 
    } 
    return rank; 
} 

Проблема в том, что он работает для всех чисел в массиве, за исключением 7. Я пытался найти его отладки, но придумал ничего.

Может ли кто-нибудь сказать мне, в чем проблема?

Answer 1

Проблема заключается в том, что даже если вы меняете low и high, цикл зависит от переменной i, которая изменяется только за счет того увеличивается в конце каждой итерации цикла. Однако условие завершения бинарного поиска должно быть в случае low >= high. Условие цикла, которое у вас есть сейчас, i < high не имеет ничего общего с отношениями между low и high, что может привести к преждевременному прекращению цикла или продолжению бинарного поиска.

То, что я хотел бы предложить, что делает инициализирует low в цикл, изменяя условия завершающего к low <= high, и делает последовательность обновления mid = (low + high)/2, так как вы делаете, что после каждой итерации для цикла, если вы не найдете номер. Однако в этот момент цикл прекратит возвращать индекс найденного числа. Вот что это будет выглядеть,

public static int findNumber(int key, int... numbers) { 
    int high = numbers.length - 1; 
    int mid = (0 + high)/2; //replaced low with 0 here 
    int rank = 0; 
    for (int low = 0; low <= high; mid = (low + high)/2) { 
     if (key < numbers[mid]) { 
      high = mid - 1; 
     } else if (key > numbers[mid]) { 
      low = mid + 1; 
     } else { 
      rank = mid; 
      return rank; 
     } 
    } 
    return rank; 
} 

EDIT: Таким образом, после некоторого тестирования, я понял, что еще одна ошибка, как вы обновляют low и high в вашем методе. Когда вы обновляете эти переменные раньше, вы просто делаете high = mid и low = mid, но это опасно, потому что, делая это, вы по-прежнему сохраняете numbers[mid] в пределах диапазона, который будет оцениваться на следующей итерации цикла. Этот номер, numbers[mid] следует исключить из диапазона, так как ключ будет либо меньше, больше или равен numbers[mid]. Если ключ меньше или больше, чем numbers[mid], тогда нет смысла держать его в будущем для следующего диапазона чисел, на которые нужно искать двоичный поиск.Таким образом, решение будет заключаться в обновлении низких и высоких значений на low = mid + 1 и high = mid - 1.

Answer 2

Проблема с петлей for. Вы ограничиваете количество проходов цикла до high, но high получает изменения из цикла. Вы имели в виду что-то вроде for (int i = low; i < numbers.length - 1; i++) { ... }?

Answer 3

Я думаю, что ваш цикл for немного ошибочен. Вместо

for (int i = low; i < high; i++) 

должно быть:

for (int i = low; i <= high; i++) 

Answer 4

Как уже говорилось, условие остановки выключен. Может быть, легче думать о состоянии остановки по-разному. Измените верхнюю и нижнюю границы, чтобы вы искали «половинки» массива. Когда вы знаете, что предмет, который вы пытаетесь найти, не существует в массиве? То есть, когда индексы пересекаются. низкий уровень выше, чем высокий. (while low <= high) { ... } В этом случае вы можете вернуть фиктивное значение, которое, как вы знаете, не должно существовать в массиве. Например, если вы сохраняете только положительные значения, возвращайте -1. В противном случае вы можете вернуть Integer (не примитивный тип) для представления индекса, и если элемент не найден, в частности, null.