java - 二进制搜索和文件读取进入无限循环

Question

我想实现二分搜索，但搜索键是外部提供的。这意味着我的硬盘中有一个文件。我想从这个文件中读取关键值。我为此目的写了一个代码。但代码进入无限循环。

这是我的代码:

public class T5 {
public static void main(String args[])throws Exception{
    double arr[]= new double[]{86.0,12.0,55.0,90.0,77.0,22.0,25.0,33.0,45.0,20.0,23.0};
    int first=0;
    int last=(arr.length)-1;
    Scanner x= new Scanner(new File("D:\\Test_1.txt"));
    while(x.hasNext()){
        double a =x.nextDouble();
        while(first<=last){
            int mid=(first+last)/2;
            if(arr[mid]==a){
                System.out.println("Search successful");
            }
            if(arr[mid]<a){
                last=mid+1;
            }
            else{
                last=mid-1;
            }

        }
    }
}
} 

我在这里提到的 Text_1.txt 文件是这样的

86.0

25.0

30.0

18.0

90.0

88.0

70.0

87.0

55.0

这里提到的数组arr[]就是要与键值进行比较的值。 arr[] 由 86.0 组成，文件有 86.0，因此搜索成功。文件的值为 25.0，arr 的值也为 25.0。于是再次搜索成功。该文件的值为 30.0，但 arr[] 没有该值。所以搜索没有成功。

这就是概念，但为什么它会进入无限循环。欢迎任何建议和讨论。

Answer 1

首先，应用二分搜索的数组应该进行排序!

您应该始终尝试可视化您的算法。具体来说，对于二分搜索，您必须想象您有左右两个边界，左边界向右移动，右边界向左移动，并且该过程继续直到它们碰撞，或者直到您找到您的元素。

对我来说很明显，你甚至没有尝试追踪你的算法......

另外，请注意，一个 while 循环位于另一个 while 循环内部。而且您永远不会在第一个循环开始时重置第一个和最后一个变量。这是错误的。

最后一件事，优先选择 first + (last - first)/2 而不是 (last + first)/2。因为，(last + first)/2 可能会溢出，而 first + (last - first)/2 则不会。

让我们将程序分解为 2 个函数，一个执行二分查找，另一个执行读取。

1)

static boolean binarySearch(double a) {
    double[] arr = {1, 2, 3, 4, 5, 6};
    Arrays.sort(arr);
    int first = 0;
    int last = arr.length - 1;

    while (first <= last) {
        int mid = first + (last - first) / 2;
        if (arr[mid] == a) {
            return true;
        } else if (arr[mid] < a) {
            first = mid + 1;
        } else /*if (arr[mid] > a)*/{
            last = mid - 1;
        }
    }
    return false;
}

2)

public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
        double d = sc.nextDouble();
        binarySearch(d);
    }
}

另外，JDK中有一个binarySearch方法，所以你的代码变成:

public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    double[] arr = {1, 2, 3, 4, 5, 6};
    Arrays.sort(arr);
    while (sc.hasNext()) {
        double d = sc.nextDouble();
        Arrays.binarySearch(arr, d);
    }
}