В данном коде пытаюсь реализовать рекурсивный алгоритм бинарного поиска. Для массива 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;
}
}
a == b
писатьabs(a - b) < eps
, гдеeps
- желаемая точность совпадения