0

我有一个学生名单，我想按姓氏对他们进行排序。学生列表看起来有点像这样：

Amanda
Dorris
Tucker
Yasmin
Zara

我想用二分法搜索这些学生，输出想要的结果。

这是我到目前为止所拥有的：

public void binarySearch(String keyword) {

    int output;

    if (fileSorted == false) {
        System.out.println("The file " + fileName + " is not sorted. Please wait while it gets sorted...");
        bubbleSort();
        System.out.println("Thank you for your patience.");
        System.out.println();
        System.out.print("Search for: ");
        keyword = elmo.nextLine();
        output = doBinarySearch(keyword);
    } else {
        output = doBinarySearch(keyword);
    }
    System.out.println(output);
}

public int doBinarySearch(String keyword) {

    int start = 0;
    int end = numStudents - 1;
    int mid;
    int result;

    while (start < end) {
        mid = start + (end - start) / 2;
        result = students[mid].returnLastName().compareToIgnoreCase(keyword);

        if (result == 0) {
            return mid;
        } else if ((end - start) <= 1 ) {
            return -1;
        } else if (result > 0) {
            start = mid;
        } else if (result < 0) {
            end = mid;
        }
    }
    return -1;
}
4

2 回答 2

2

线

mid = ((end - start) / 2);

是错的。您需要设置mid为（大致）和的中点start，end所以

mid = start + (end - start) / 2;

或者

mid = (end + start) / 2;

如果你不怕溢出。

有了你所拥有的，mid总是在数组的前半部分。

另外，你有你的案子

    } else if (result > 0) {
        start = mid;
    } else if (result < 0) {
        end = mid;
    }

错误的。

result = students[mid].returnLastName().compareToIgnoreCase(keyword);

当姓氏的students[mid]字典序大于时返回一个正数keyword，所以你需要改变end，而不是start。

于 2013-06-15T23:24:57.043 回答
0

而不是在循环条件中使用不等式while (start != end)——使用while (start < end). 这是典型的做法。当您测试相等性时，您会假设start并且end在每次迭代中只改变一个，这可能不一定是真的。

于 2013-06-15T23:21:12.770 回答