Insert into an already-sorted list

Question

With Java, I have a class, known as TestClass, which has a member named Name, which is a string. I also have an ArrayList of this type, which is already sorted alphabetically by Name. What I want to do is find the best index in which to put a new instance of TestClass. The best approach I could come up with so far is this:

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

Essentially, Break the array in half, check to see if your value goes before, after, or at that point. If it's after, check the first half of the array. Other wise, check the second half. Then, repeat. I understand that this method only tests by the first character, but that's easily fixed, and not relevant to my main problem. For some scenarios, this approach works well enough. For most, it works horribly. I assume that it isn't finding the new pivot point properly, and if that's the case, how would I fix it?

Edit: For clarification, I'm using this for an inventory system, so I'm not sure a LinkedList would be appropriate. I'm using an ArrayList because they are more familiar to me, and thus would be easier to translate into another language, if needed (which is likely, at the moment, might be moving over to C#). I'm trying to avoid things like Comparable for that reason, as I'd have to completely re-write if C# lacks it.

Edit part Duex: Figured out what I was doing wrong. Instead of using the previous pivot point, I should have been setting and changing the boundaries of the area I was checking, and creating the new pivot based on that.

Answer 1

It might not be a good idea to use a SortedSet (e.g. a TreeSet) for this, because Set‘s don't allow duplicate elements. If you have duplicate elements (i.e. TestClass instances with the same name), then a List should be used. To insert an element into an already sorted list is as simple as this:

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

This code requires Java 8 or later, but can be rewritten to work in older Java versions as well.

Answer 2

As already pointed out, there is no reason to implement this by yourself, simple code example:

    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

(Based on How to find the index of an element in a TreeSet?)