21天算法训练--顺序表

          查找是计算机中数据结构最常用的操作方式，对于线性数据结构，如果按照记录存放在线性表中的自然顺序查找 通常称为顺序查找。

1. ​顺序查找

     又称作线性查找，通常理解为对线性数据结构的查找，比如数组，链表。它十基本的查找方式，简单直接。 

        生活中常见的例子：比如按照页码顺序查找字典。

时间复杂度：假设数据数目为n，i项查中的次数为i 平均查找次数为1+2+3+...+n 为(1+n)*n/2 

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

它的定义是这样的：

 其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。上述是查找成功的情况。

当然，有查找成功，就有查找不成功，即要查找元素不在查找表中。针对不同查找方式的查找成功与不成功，

一个算法的ASL越大，说明时间性能差，反之，时间性能好，这也是显而易见的。

在顺序查找(Sequence Search)表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci（第i个元素的比较次数）在于这个元素在查找表中的位置，如第0号元素就需要比较一次，第一号元素比较2次......第n号元素要比较n+1次。所以Ci=i；所以 

            可以看出，顺序查找方法查找成功的平均 比较次数约为表长的一半。

当待查找元素不在查找表中时，也就是扫描整个表都没有找到，即比较了n次，查找失败。

            

活动地址：CSDN21天学习挑战赛

2，代码实现

#include
using namespace std;
int a[101]={90,3,2,1,-5,9,10,23,45,77};
int main(){
  int n,key;
   cin>>n>>key;
   for (int i=0;i
        cin>>a[i];
   }
   for (int i=0;i
            if (a[i]==key) {
            cout<<"found"<              return 0;
            }
        }
   cout<<"not found"<    return 0;
}
 

3  查找失败的优化

 对于顺序查找算法如果失败的情况下，需要查找N次这个效率其实是很低的，如果顺序表中的关键字是有序排列的，当比较到一定程度就可以提前结束循环。提高查找效率，实际生产中更有用，可以避免数据分布不均匀、恶意查找的情况，带来的性能下降。

//假设数据是递增的

#include 
#include 
using namespace std;
int a[101]={90,3,2,1,-5,9,10,23,45,77};
int main(){
  int n,key,i;
   cin>>n>>key;
   for (i=0;i
        cout<" ";
   }
   cout<
   sort(a,a+n);
    for ( i=0;i
        cout<" ";
   }
   for ( i=0;i
		}
	
	  cout<
	if (a[i] ==key) {
		cout<<" found a["<"]"<
		} else {
		cout<<"not found with ending index "<
		} 
   cout<
   return 0;
}

4. 链表中查找的实现

链表和数组实现思路差不多

参考文献：

数据结构概述

​