使用文件读取的二进制搜索进入无限循环

Question

我想执行二进制搜索，但提供的搜索关键字 externally.That 意味着我的硬盘中有一个文件。我想从这个文件中读取键值。为此，我写了一段代码。但是代码进入无限循环。

这是我的代码：

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[]就是key值要比较的值。 arr[] 由 86.0 组成，文件具有 86.0，因此搜索成功。该文件有 25.0，arr 也有值 25.0。于是再次搜索成功。该文件的值为 30.0，但 arr[] 没有。所以搜索不成功。

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

Answer 1

首先，应用二分查找的数组应该被排序！

您应该始终尝试可视化您的算法。特别是对于二进制搜索，你必须想象你有左右两个边界，左边的边界向右移动，右边的边界向左移动，这个过程一直持续到它们发生碰撞，或者直到你找到你的元素。

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

另外，请注意您在另一个内部有一个 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);
    }
}

使用文件读取的二进制搜索进入无限循环

Binary search with file reading goes infinite loop

java

arrays

file

binary-search

java.util.scanner