Бинарный поиск возвращал неправильный ответ много раз

Question

Я реализовал итеративный алгоритм двоичного поиска, который возвращает индекс найденного элемента (-1, если элемент отсутствует в массиве):

public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

Когда я пытаюсь проверить его наэлемент, которого нет в массиве, возвращает правильный ответ, когда я попробовал его с массивом: {1,5,23,111}, а целью является число 5, он вернул правильный результат, который в данном случае равен 1, однако когда я попытался с этимтот же массив, но число 111 вернуло -1, я также пытался использовать разные массивы и несколько целевых чисел, и много раз он возвращал -1, хотя число присутствует в массиве, есть какая-нибудь помощь в том, почему это происходит?

Answer 1

Ваше продвижение влево / вправо назад. Когда элемент в текущей позиции mid меньше цели, тогда вам нужно искать правую половину, а когда элемент в текущей позиции mid больше цели (блок else), вам нужнодля поиска левой половины.

Единственная причина, по которой вы нашли 5 правильно, состоит в том, что mid оказался правильным в первой итерации.

Переключите ваши операторы в else if иelse блоков.

else if (array[mid] < target) { left = mid + 1; }
else { right = mid - 1; }

Или наоборот изменить смысл сравнения для условия else if.

else if (array[mid] > target) { right = mid - 1; }
else { left = mid + 1; }

Answer 2

В вашей программе есть логическая проблема.

1. Первая проблема - использование else с условием if, содержащим оператор return. Поскольку метод будет return, когда условие if равно true, установка else бесполезна. Использование else необходимо для выбора любого из двух вариантов (т. Е. Не обоих). После использования оператора return с первым параметром вы уже запрещаете второй параметр.
2. Вторая проблема - неправильное вычисление переменных right и left. Логика должна быть: Игнорировать левую половину, если target больше, чем число в mid, и для этого просто продвинуться left на одну позицию за mid;в противном случае (т. е. если target на less, чем число в mid), игнорируйте правую половину, переместив right назад на одну позицию.

Ниже приводится рабочая программа:

public class BinarySearchDemo {

    public static void main(String[] args) {
        int arr[] = { 1, 5, 23, 111 };
        System.out.println(binarySearch(arr, 23));
        System.out.println(binarySearch(arr, 20));
    }

    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - 1) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

Выход:

2
-1

Answer 3

Хотел добавить как комментарий, но пока не может комментировать

После того, как вы исправили свой код с правильной логикой (как в ответах выше), вот что можно улучшить в вашем коде:Не делай этого: int mid=(left+right)/2;Сделайте это: int mid = low + ((high - low) / 2); или это int mid = (low + high) >>> 1;

См. Этот пост .

Answer 4

Проблема в том, что вы обновляете left и right. Вы обновляете их в неправильных операторах if.

Когда array[mid] < target, вы хотите обновить указатель left и выполнить поиск в правом подмассиве, и наоборот.

Итак, ваши обновлениядолжно выглядеть так:

else if (array[mid] < target) { left = mid + 1; } 
else { right = mid - 1; }