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

2019-11-14 14:07:22

字體：大中小

來源：轉載

供稿：網友

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