4.6.3 顺序表按值查找操作的时间复杂度是多少

在顺序表中进行按值查找实现了一个比较运算，比较的次数与给定值在表中的位置和表长有关。当给定值与第一个数据元素相等时，比较次数为1；当给定值与最后一个元素相等时，比较次数为n。所以，平均比较次数为(n+1)/2，时间复杂度为O(n)。因为顺序表是用连续的空间存储数据元素，所以有很多种按值查找方法。如果顺序表是有序的，建议用折半查找法，这样可以较大地提高效率。