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

时间:2021-08-30 16:02:58

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

线性查找:Contains,Find,IndexOf都是线性查找。

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

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

测试结果:

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

测试代码:

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