版權(quán)聲明：本文源自簡(jiǎn)書tianma，轉(zhuǎn)載請(qǐng)務(wù)必注明出處：http://www.reibang.com/p/f6ec95118574
定義
順序查找又稱為線性查找，其算法思路是從數(shù)組中的第一個(gè)（或最后一個(gè)）記錄開始，將數(shù)組中元素逐個(gè)與需要查找的關(guān)鍵字進(jìn)行比對(duì)，若發(fā)現(xiàn)有相等的劳澄，則查找成功；若始終未能相等蜈七，則查找失敗秒拔。
Java實(shí)現(xiàn)
// 定義接口
interface Searcher {
/**
* 從數(shù)組array中查找關(guān)鍵字key,如果存在則返回該關(guān)鍵字在數(shù)組中任意出現(xiàn)的位置(不局限于首次或者末次之類的),否則返回-1
*/
int search(int[] array, int key);
}
/**
* 順序表查找,時(shí)間復(fù)雜度為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是標(biāo)準(zhǔn)的線性查找，這里有缺陷：在循環(huán)中每個(gè)循環(huán)實(shí)際上需要判斷兩次(一次是否相等,一次是否越界)飒硅，如何改進(jìn)呢砂缩？其實(shí)就是設(shè)置“哨兵”：
/**
* 優(yōu)化的順序表查找,時(shí)間復(fù)雜度O(n),但是比普通順序表查找效率高
*/
class OptimizedLinearSearcher implements Searcher {
// 相比單純的線性查找每次for循環(huán)需要判斷兩次,這里設(shè)置關(guān)鍵字值(即哨兵)，可以讓每次for循環(huán)只判斷一次
// 當(dāng)數(shù)據(jù)量比較大時(shí),如果單純從線性查找角度看,優(yōu)化后的線性搜索優(yōu)勢(shì)明顯
@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]作為哨兵
// 這里"哨兵"也可以放在數(shù)組尾部
int i = len - 1;
while (array[i] != key) { // 每次循環(huán)少判斷一個(gè)
i--;
}
if (i == 0) // 從數(shù)組尾部一直查找到array[0]才找到,說(shuō)明不存在
return -1;
return i;
}
}
不論是線性查找還是改進(jìn)后的線性查找三娩，其時(shí)間復(fù)雜度都為O(n)
