List<T>線性查找和二分查找BinarySearch效率分析，listbinarysearch

List<T>線性查找和二分查找BinarySearch效率分析，listbinarysearch

今天因為要用到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("");
        }