java - 插入到一个已经排序的列表中

Question

在 Java 中，我有一个名为 TestClass 的类，它有一个名为 Name 的成员，它是一个字符串。我还有一个这种类型的 ArrayList，它已经按名称的字母顺序排序了。我想要做的是找到放置 TestClass 新实例的最佳索引。到目前为止，我能想到的最佳方法是:

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

本质上，将数组分成两半，检查您的值是在该点之前、之后还是在该点。如果在之后，请检查数组的前半部分。否则，请检查下半部分。然后，重复。我知道此方法仅通过第一个字符进行测试，但这很容易修复，并且与我的主要问题无关。对于某些场景，这种方法效果很好。对于大多数人来说，它的效果非常糟糕。我假设它没有正确找到新的枢轴点，如果是这种情况，我该如何解决？

编辑:为澄清起见，我将其用于库存系统，因此我不确定 LinkedList 是否合适。我使用 ArrayList 是因为它们对我来说更熟悉，因此如果需要的话更容易翻译成另一种语言(目前可能会转移到 C#)。出于这个原因，我试图避免像 Comparable 这样的东西，因为如果 C# 缺少它，我将不得不完全重写。

编辑部分 Duex:找出我做错了什么。我不应该使用之前的枢轴点，而应该设置和更改我正在检查的区域的边界，并基于此创建新的枢轴点。

Answer 1

为此使用 SortedSet(例如 TreeSet)可能不是一个好主意，因为 Set 不允许重复元素。如果您有重复的元素(即具有相同名称的 TestClass 实例)，则应使用 List。向已排序的列表中插入一个元素就这么简单:

void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

此代码需要 Java 8 或更高版本，但可以重写以在旧的 Java 版本中工作。