演算法 - 線性搜尋法(Linear Search) 循序搜尋法(Sequential Search )
YehYeh\'s Notepad yehyeh@gmail.com 

[演算法(Algorithm)] 線性搜尋法(Linear Search)

  • 線性搜尋法(Linear Search)循序搜尋法(Sequential Search)
  • 線性搜尋法類型
    • 無崗哨(衛兵)線性搜尋(Non-Sentinel Linear Search)
      • 直接對數列由右至左,或由左至右一一比對是否有與鍵值相同的元素
      • 需比對陣列值是否與鍵值相同陣列是否結束
    • 崗哨(衛兵)線性搜尋(Sentinel Linear Serach)
      • 直接對數列由右至左,或由左至右一一比對
      • 將鍵值放在陣列的第一個最後一個元素,並把這個元素當成崗哨(衛兵)
        • 一定可以找到與鍵值相同的元素 避免檢查陣列是否結束
      • 因為省下一次比較的時間,當資料很大時,時間約為無崗哨線性搜尋的一半(時間複雜度仍為Ο(n))
  • 特性:
    • 資料不需事先排序
    • 支援隨機存取(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;
    };