二进制 Search/Insert 方法未正确插入

Question

我需要一个按字母顺序排序的学生数据库，因此我决定通过正确插入学生来保持他们的排序。因此，我决定使用插入方法实现二分查找，以在插入时保持排序。

但是，由于某种原因，它插入不正确，数据库不再排序。我知道这与我使用 .compareToIgnoreCase() 方法的逻辑有关。这是我的代码：

private Student[] binaryInsert(Student student, int min, int max) {
    int mid = (min + max) / 2;
    if (min > max) {
        return insert(studentDatabase, student, -1);
    }
    if (min == max) {
        if (studentDatabase[mid].compareToIgnoreCase(student)) < 0) {
            return insert(studentDatabase, student, mid + 1);
        } else {
            return insert(studentDatabase, student, mid - 1);
        }
    } else if (studentDatabase[mid].compareToIgnoreCase(student)) < 0) {
        return binaryInsert(student, mid + 1, max);
    } else {// last possibility: a[mid] > x
        return binaryInsert(student, min, mid - 1);
    }
}

public Student[] insert(Student[] database, Student object, int i) {
    Student[] newDatabase = new Student[database.length + 1];
    if (i == -1) {
        for (int j = 1; j < newDatabase.length; j++) {
            newDatabase[j] = database[j - 1];
        }
        newDatabase[0] = object;
    } else {
        for (int x = 0; x < i; x++) {
            newDatabase[x] = database[x];
        }
        newDatabase[i] = object;
        for (int x = i + 1; x < newDatabase.length; x++) {
            newDatabase[x] = database[x - 1];
        }
    }
    return newDatabase;
}

我的输入：

STUDENT/NAD86/RAFAEL/NADAL/1986/SPAIN
STUDENT/DJO87/NOVAK/DJOKOVIC/1987/SERBIA
STUDENT/FED81/ROGER/FEDERER/1981/SWITZERLAND
STUDENT/STA86/ALEX/STAIRS/1998/AMERICA

我的输出

FED81: ROGER FEDERER, 1981, SWITZERLAND, 0.0
DJO87: NOVAK DJOKOVIC, 1987, SERBIA, 0.0
NAD86: RAFAEL NADAL, 1986, SPAIN, 0.0
STA86: ALEX STAIRS, 1998, AMERICA, 0.0

FED81 是问题儿童。如果我重新排列输入，它确实有效，但我做不到。

提前感谢您的帮助！

编辑：应该注意的是，我尝试了相同的过程，但使用的是整数，它在我的所有测试中都有效。

Answer 1

多亏了 Joop Eggen，我才能够让它工作。解决方案是从 insert(studentDatabase, student, mid - 1) 方法调用中取出“- 1”。

修复是因为 a[i] 之前的插入点在 i，而不是 i - 1。

感谢 Joop Eggen！

二进制 Search/Insert 方法未正确插入

Binary Search/Insert Methods not inserting correctly

java

database

sorting

insert

binary-search