20
Июл
2021

Почему не работает алгоритм бинарного поиска

В данном коде пытаюсь реализовать рекурсивный алгоритм бинарного поиска. Для массива arr, на котором я тестирую работу этого алгоритма, он не работает. Для тестирования я после каждого рекурсивного цикла вывожу на консоль новый полученный массив. Для указанного массива, в котором мы ищем число 6.6, вывод такой:

1.1 1.3 1.6 3.1 4.1 4.9 5.1 5.3 5.5 6.6 6.9 9.4 9.7 11.1 13.8 14.1 19.5 23.6 55.1 99.1
Середина массива: 6.9
Новый массив:  1.1 1.3 1.6 3.1 4.1 4.9 5.1 5.3 5.5 6.6
Середина массива: 4.9
Новый массив:  5.1 5.3 5.5 6.6
Середина массива: 5.5
Новый массив:  6.6
false

Судя по false, искомый элемент 6.6 он не находит, несмотря на то, что в последней итерации создается новый массив из одного элемента {6.6} и на нём должен снова быть вызван метод find, который должен его идентифицировать как середину массива и после проверки if(arr[arr.length/2] == num) должен вернуть true. Но метод, видимо, не вызывается, в результате чего метод выходит из рекурсивного цикла if и возвращает false. Почему так происходит?

При этом если на вход для данного метода сразу запихнуть массив из одного искомого элемента: double[] arr = {6.6};, то бинарный поиск возвращает true, то есть находит этот элемент, что ещё больше меня запутывает. Причину этого мне бы тоже хотелось прояснить.

Мой код:

import java.util.Arrays;
import java.util.Random;

public class Main{
    public static void main(String[] args) {
        double[] arr = {1.3, 4.1, 5.5, 9.4, 19.5, 3.1, 5.1, 13.8, 11.1, 4.9, 5.3 ,9.7 , 1.1, 6.9 ,99.1,1.6,55.1,23.6,14.1,6.6};
        //double[] arr = {6.6};
        Arrays.sort(arr);
        for(double i: arr){
            System.out.print(" "+ i);
        }
        System.out.println();
        System.out.println(BinarySearch.find(6.6, arr));

    }
}

class BinarySearch{
    public static boolean find (double num, double[] arr){

        if(arr[arr.length/2] == num){
            return true;
        }
        else if (arr[arr.length/2] < num){
            double[] newHigherArr = Arrays.copyOfRange(arr, (arr.length/2)+1, arr.length);
            
            // Выводы для тестов: начало
            System.out.println("Середина массива: " + arr[arr.length/2]);
            System.out.print("Новый массив: ");
            for(double i: newHigherArr){
                System.out.print(" " + i);
            }
            System.out.println();
            // Выводы для тестов: конец
            
            
            find(num, newHigherArr);
            
        } else if (arr[arr.length/2] > num){
            double[] newLowerArr = Arrays.copyOfRange(arr, 0, arr.length/2);
            
            // Выводы для тестов: начало
            System.out.println("Середина массива: " + arr[arr.length/2]);
            System.out.print("Новый массив: ");
            for(double i: newLowerArr){
                System.out.print(" " + i);
            }
            System.out.println();
            // Выводы для тестов: конец
            
            find(num, newLowerArr);
        }
        return false;
    }
}

Источник: https://ru.stackoverflow.com/questions/1306934/%D0%9F%D0%BE%D1%87%D0%B5%D0%BC%D1%83-%D0%BD%D0%B5-%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%B0%D0%B5%D1%82-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%B1%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B3%D0%BE-%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0

Тебе может это понравится...

Добавить комментарий