版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/f6ec95118574
定义
顺序查找又称为线性查找，其算法思路是从数组中的第一个（或最后一个）记录开始，将数组中元素逐个与需要查找的关键字进行比对，若发现有相等的，则查找成功；若始终未能相等，则查找失败。
Java实现
// 定义接口
interface Searcher {
/**
* 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
*/
int search(int[] array, int key);
}
/**
* 顺序表查找,时间复杂度为O(n)
*/
class LinearSearcher implements Searcher {
@Override
public int search(int[] array, int key) {
int len = array.length;
for (int i = 0; i < len; i++) {
if (array[i] == key)
return i;
}
return -1;
}
}
LinearSearcher是标准的线性查找，这里有缺陷：在循环中每个循环实际上需要判断两次(一次是否相等,一次是否越界)，如何改进呢？其实就是设置“哨兵”：
/**
* 优化的顺序表查找,时间复杂度O(n),但是比普通顺序表查找效率高
*/
class OptimizedLinearSearcher implements Searcher {
// 相比单纯的线性查找每次for循环需要判断两次,这里设置关键字值(即哨兵)，可以让每次for循环只判断一次
// 当数据量比较大时,如果单纯从线性查找角度看,优化后的线性搜索优势明显
@Override
public int search(int[] array, int key) {
int len = array.length;
if (len == 0) // array为空,返回-1
return -1;
if (array[0] == key)
return 0;
array[0] = key; // array[0]不是key,那么将key赋值给array[0],将array[0]作为哨兵
// 这里"哨兵"也可以放在数组尾部
int i = len - 1;
while (array[i] != key) { // 每次循环少判断一个
i--;
}
if (i == 0) // 从数组尾部一直查找到array[0]才找到,说明不存在
return -1;
return i;
}
}
不论是线性查找还是改进后的线性查找，其时间复杂度都为O(n)
