主页 / 问题 / 1306934
Accepted
faritowich
Asked:2022-07-20 15:56:18 +0000 UTC2022-07-20 15:56:18 +0000 UTC

为什么二进制搜索算法不起作用

  • 772

在这段代码中，我试图实现一个递归二进制搜索算法。对于我正在测试此算法的数组arr，它不起作用。为了测试，在每个递归循环之后，我将新的结果数组打印到控制台。对于指定的数组，我们在其中查找 number 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;
    }
}
java

1 个回答

  1. Best Answer

    它可以是这样的：

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

    if(arr[arr.length/2] !=num && arr.length/2==0) //<--
        return false; //<--
    
    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();
        // Выводы для тестов: конец


        return 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();
        // Выводы для тестов: конец

         return find(num, newLowerArr); //<--
    }
    return false;
}
    • 1

相关问题