找到列表中元素的最佳位置

Question

我有按特定顺序填充的List集合(要求是,此顺序无法更改).此列表包含实体类型对象.

在列表的初始填充之后,我需要插入更多来自另一个数据源的对象.需要将这些对象插入特定位置,以便排序正确.

例如,如果初始列表具有以下元素

1. AAA
2. AAB
3. AAC
4. ACC
5. ADA

初始填充后我想插入"ABB"元素,需要插入3到4之间.

目前,我有以下方法为新元素找到正确的位置.

    private static int FindPositionForArticle(string word)        
    {
        string key = word.ToLower();
        for (int i = word.Length; i >= 0; i--)
        {
            if(i < word.Length)
                key = key.Remove(i, 1);

            int pos = 0;
            int insertPos = 0;
            foreach(ArticleEntity article in list)
            {
                if(article.Text.ToLower().StartsWith(key))
                    insertPos = pos;
                else if (!article.Text.ToLower().StartsWith(key) && insertPos > 0)
                    return insertPos++;
                pos++;
            }
        }
        return 0;
    }

这种方法背后的目的是:

1. 拿出需要插入的"单词",尝试找到与"单词"同名的元素的位置

2. 如果未找到任何内容,请从"单词"中删除最后一个字符并再次搜索.

3. 重复删除最后一个字符,直到找到最佳位置.

不幸的是我的方法有bug(实现不正确).目前我的方法表明最佳位置为0,这是完全错误的.

如果您想使用我的示例代码,您可以在以下位置下载:

http://dl.getdropbox.com/u/204110/FindPosition.cs.txt

先感谢您.

Answer 1

int index = list.BinarySearch(word);

如果index为正数或零,则在列表中找到该项.如果为负数,则它包含列表中下一个最高项的索引的按位补码.

所以,为此:

List<string> list = new List<string>{"AAA","AAB","AAC","ACC","ADA"};
int index = list.BinarySearch("ABB"); // => -4
int insertIndex = ~index; // => 3
list.Insert(insertIndex, "ABB");