顺序表查找

顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的元素的关键字与给定的关键字k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字与k相等的元素，则查找失败。

​ 例如定义一个int类型数组，在此数组中查找某一个元素是否存在，那么其对应的的顺序查找算法如下所示：

int sq_find(int arr[], int n, int key) //n为数组元素个数，key为要查找的元素
{
  for (int i = 0; i < n; i++)
  {
​    if (arr[i] == key) //如果找到key值，则返回角标i
​      return i;
  }
  return -1;
}

观察以上算法发现，在for循环中，算法近乎一半时间消耗在了数组的边界检查上面，为了减少边界检查的时间消耗，可以设置一个“监视哨兵”，“监视哨兵”往往是数据中一个元素的关键字。如果是对整型数组中的元素进行查找，那么该变量一般是数值型变量，变量的赋值就相当于哨兵的设置，当数组中出现与哨兵相等的值时，说明此时查找成功，或者整个数组查找完毕，但没有找到符合条件的元素，查找失败。

在顺序查找中，往往把第一个或最后一个位置的元素设置为哨兵，例如将上述算法改进，在其中设置一个哨兵，其代码如下所示：

int sq_find(int arr[], int n, int key) //n为数组元素个数，key为要查找的元素
{
  int i = n;
  arr[0] = key; //arr[0]设置为哨兵
  while (arr[i] != key) //若数组中无key,则一定会得到arr[0] = key
​    i--;
  return i; //查找成功时返回角标i，如果失败，i为0，返回的是0
}

​ 在这个算法中，从查找表的尾部开始查找，由于设置了arr[0]=key这个哨兵， arr[0]不能存入有效数据，查找时只是在arr[1]~arr[n]这个范围内查找。每一次查找都与arr[0]比较，如果与之相等则查找成功，返回i的值；如果arr[1]~arr[n]之间没有key值，则查找失败。

​ 在尽头放置哨兵，避免了查找过程中对查找位置是否越界的多次判断。对于少数数据的查找没有什么影响，但对于大量数据的查找来说，效率提高还是很大的。

顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构，既可用于无序表的查找也可用于有序表的查找。最好的情况是第一次查找就能找到，算法时间复杂度为O(1)，最坏的情况是将n个数据遍历一遍，算法时间复杂度为O(n)，平均下来算法时间复杂度为O(n/2)，因为关键字出现在任何一个位置的概率是相同的，所以算法最终的复杂度还是O(n)。