List<T>线性查找和二分查找BinarySearch效率分析

一、测试一

    public  class Test
    {
        
        public static void Main(string[] args) 
        {
            int bookIndex;
            string[] book1 = { "book1", "book7", "book3" };
            bookIndex = Array.BinarySearch(book1,"book3");
            Console.WriteLine(bookIndex);

            Array.Sort(book1);
            bookIndex = Array.BinarySearch(book1, "book3");
            Console.WriteLine(bookIndex);
            Console.ReadLine();
        }
    }

以上代码，得到的结果是

-2

1

为什么同样是BirnarySearch，得到的结果不一样呢。

那是因为BirnarySearch用的是二分算法，在用BirnarySearch进行检索前，需要先对数组进行排序。

然后又会有一个疑问，BirnarySearch实际上是来取对象在数组中的索引值。通常我们用的取索引值方法是IndexOf，那么BirnarySearch和IndexOf又有什么区别呢。

BinarySearch是二进制搜索算法，复杂度为O(log n)，效率更高，但需要先排序。

IndexOf是线性搜索算法，复杂度为O(n)，一般来说只适用于简单类型。

二、测试二

今天因为要用到List的查找功能，所以写了一段测试代码，测试线性查找和二分查找的性能差距，以决定选择哪种查找方式。

线性查找：Contains，Find，IndexOf都是线性查找。

二分查找：BinarySearch，因为二分查找必须是对有序数组才有效，所以查找前要调用List的Sort方法。

结论：如果List项的个数比较小，用线性查找要略快于二分查找，项的个数越多二分算法优势越明显。可根据实际情况选用适合的查找方式。

测试结果：

测试代码：

        private void button1_Click(object sender, EventArgs e)
        {            
            TestFind(10);
            TestFind(30);
            TestFind(70);
            TestFind(100);
            TestFind(300);
            TestFind(1000);
        }
 
        private void TestFind(int aItemCount)
        {
            listBox1.Items.Add("测试：列表项个数:" + aItemCount + ",查询100万次");
            int nTimes = 1000000;
            int nMaxRange = 10000;      //随机数生成范围           
            Random ran = new Random();
            List<int> test = new List<int>();
            for (int i = 0; i < aItemCount; i++)
            {
                test.Add(ran.Next(nMaxRange));
            }
 
            int nHit = 0;
            DateTime start = DateTime.Now;
            for (int i = 0; i < nTimes; i++)
            {
                if (test.IndexOf(ran.Next(nMaxRange)) >= 0)
                {
                    nHit++;
                }
            }
            DateTime end = DateTime.Now;
 
            TimeSpan span = end - start;
            listBox1.Items.Add("一般查找用时：" + span.Milliseconds + "ms， 命中次数：" + nHit);
 
            nHit = 0;
            start = DateTime.Now;
            test.Sort();
            for (int i = 0; i < nTimes; i++)
            {
                if (test.BinarySearch(ran.Next(nMaxRange)) >= 0)
                {
                    nHit++;
                }
            }
            end = DateTime.Now;
 
            span = end - start;
            listBox1.Items.Add("二分查找用时：" + span.Milliseconds + "ms， 命中次数：" + nHit);
            listBox1.Items.Add("");
        }