【アルゴリズム】線形探索

Contents

1. 線形探索とは
2. 線形探索(位置を返す)
3. 番兵を用いた場合(位置を返す)
4. 線形探索(bool)
5. 番兵を用いた場合(bool)
6. 参照

線形探索とは

配列の先頭から、各要素の値が目的の値と等しいかどうかを、順番に調べること。
目的の値が見つかった時点で、その位置(key)を返す。
最後まで見つからなかった場合には、その事を示す値を返す(NOT_FOUND)。
※以下、phpの場合

線形探索(位置を返す)

function linear_search($array,$target){
    for($i=0;$i<count($array);$i++){//0 < i < n-1
        if($array[$i]==$target){//a[i] == key
            return $i;//位置を返す
        }
    }
    return "NOT_FOUND";
}
$array=[1,4,5,6,7,8,2];
$a = linear_search($array,8);
$b = linear_search($array,18);
var_dump($a);//int(5)
var_dump($b);//string(9) "NOT_FOUND"

番兵を用いた場合(位置を返す)

番兵とはループ制御の簡略化のために使う値で、比較演算の数が番兵を使うと異なる。
番兵を使わない場合には、keyと比較演算の2つを使用しているが、番兵を使うと、不等価演算1つで済む。

function linear_search($array,$target){
    $i = 0;
    $n = count($array);
    $array[$n] = $target;
    
    while($array[$i] != $target)$i++;
    if($i == $n){
     return "NOT_FOUND";   
    }
    return $i;
}
$array=[1,4,5,6,7,8,2];
$a = linear_search($array,8);
$b = linear_search($array,18);
var_dump($a);//int(5)
var_dump($b);//string(9) "NOT_FOUND"

boolで見ると違いが見えやすい。

線形探索(bool)

function linear_search($array,$target){
    for($i=0;$i<count($array);$i++){
        if($array[$i]==$target){
            return true;
        }
    }
    return false;
}

番兵を用いた場合(bool)

function linear_search($array,$target){
    $i = 0;
    $n = count($array);
    $array[$n] = $target;
    
    while($array[$i] != $target)$i++;    
    return $i != $n;
}

以上。