[演算法(Algorithm)] 線性搜尋法(Linear Search)
- 線性搜尋法(Linear Search)即循序搜尋法(Sequential Search)
- 線性搜尋法類型
- 無崗哨(衛兵)線性搜尋(Non-Sentinel Linear Search)
- 直接對數列由右至左,或由左至右一一比對是否有與鍵值相同的元素
- 需比對陣列值是否與鍵值相同、陣列是否結束
- 崗哨(衛兵)線性搜尋(Sentinel Linear Serach)
- 直接對數列由右至左,或由左至右一一比對
- 將鍵值放在陣列的第一個或最後一個元素,並把這個元素當成崗哨(衛兵)
- 一定可以找到與鍵值相同的元素 避免檢查陣列是否結束
- 因為省下一次比較的時間,當資料很大時,時間約為無崗哨線性搜尋的一半(時間複雜度仍為Ο(n))
- 無崗哨(衛兵)線性搜尋(Non-Sentinel Linear Search)
- 特性:
- 資料不需事先排序
- 支援隨機存取(Random Access)與循序存取(Sequential Access)機制
- 時間複雜度為Ο(n) 線性
- 時間複雜度(Time Complexity)
- (1+2+3+...+n)/n = (n+1)/2 Ο(n)
- Demo(無崗哨):
- Demo(崗哨):
- 演算法
var nonSentinelLinearSearch = function(data, key){ var index = 0; while(index < data.length) if(data[index++] == key) return index-1; return -1; // -1代表搜尋不到 };
var sentinelLinearSearch = function(data,key){ var index = 0; data.push(key); // 將鍵值加到陣列尾端作為崗哨 while(data[index++] != key){} data.pop(key); // 移除崗哨 return (--index == data.length) ? -1 : index; };