顺序查找数组中元素各方法详解

查找数组内元素方法，最普遍的方式就是遍历一次数组，时间复杂度为O(n)。就这遍历一次数组其实也还有很多写法，这里介绍三种方法，基本一样，有些代码细节的修改。

1.顺序查找数组中元素，正常写法

typedef int ElementType ;

int seqSearch1(ElementType ET[], int length, ElementType K)

{

int Index = length-1;

for(int i=Index; i>=0 || ET[i] != K; --i)

return i;

}

这种方法是非常普遍，第一个参数是待查找的数组ET，第二个参数是数组的长度length（因为C++中数组是不知道自己长度的），第三个参数是待查找元素。

查找方法：从数组尾往数组头查找，for循环跳出条件是（i>=0 || ET[i] != K），i>=0用于判断数组查找到头未找到，ET[i] != K用于判断找到元素跳出循环，最后返回数组下标。

2.顺序查找数组中元素，数组长度在0位

typedef int ElementType ;

int seqSearch2(ElementType ET[], ElementType K)

{

int Index = ET[0] - 1; //数组长度

for(int i=Index; i>0 || ET[i] != K; --i)

return i;

}

seqSearch2函数少了一个参数，数组长度。这里用了一个方法，将数组的0下标位存数长度，其它部份与seqSearch1函数基本一致。

3.顺序查找数组中元素，数组长度在0位，加入“哨兵”

typedef int ElementType ;

int seqSearch3(ElementType ET[], ElementType K)

{

int Index = ET[0] - 1;

ET[1] = K; //“哨兵”

for(int i=Index; ET[i] != K; --i)

return i;

}

seqSearch3函数加入了另一个方法“哨兵”。在查找前先将数组1下标位存待查找值，这样做的好处就是不用在循环体内每次判断下标（i>0），因为如果找到就直接返回下标，如果数组内本身没有K元素，哪就会找到1下标时返回。

注：但也还有更高效的查找算法，二分查找。