java - 二分查找 - 错误

Question

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

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;
}

Answer 1

线路

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 ，而不是开始。