PowerShellで実装してみるサーチアルゴリズム(リニアサーチ、バイナリサーチ）

PowerShellでサーチアルゴリズムを実装してみました。

PowerShellで実行するいいところは、環境の設定に時間をかけず、この手の勉強ならすぐできることですね。

今回実装したのはリニアサーチ、バイナリサーチの2種類です。

サーチアルゴリズム
リニアサーチ
1. ソースコード
2. 実行
バイナリサーチ
1. ソースコード
2. 実行
参考情報
1. 環境

サーチアルゴリズム

「リストデータからキーを探す」アルゴリズムのことをサーチアルゴリズムといいます。

代表的なサーチアルゴリズムとして、下記の3つがあります。

リニアサーチ（別名：線形探索）
バイナリサーチ（別名：二分探索）
ハッシュ法

本記事では上記のうち基礎的な内容の１．と２．について、Windowsに標準搭載のPowerShellで実装します。

アルゴリズムの内容を分かりやすくするため、List Class等は作成せず配列を使用します。

配列データに対して検索し、ヒットした値の位置を返します。

リニアサーチ

まずはリニアサーチです。

こちらは配列を先頭から順に検索して、見つかったらその位置を返却するサーチです。

ソースコード

実際に検索する部分をlinearSearch関数として切り離しています。

検索データの配列と見つけたい値を、引数としてlinearSearch関数に渡して実行します。

linearSearch.ps1

# search function
function linearSearch([array]$data, [int]$target){

    for($i = 0; $i -lt $data.Length; $i++){
    
        if($data[$i] -eq $target){
            return $i
        }
    }
    
    return -1
}

#position= (0, 1, 2, 3, 4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,  15)
$array1 = @(0, 1, 2, 4, 5, 15, 23, 26, 30, 31, 33, 35, 50, 75, 99, 100)

Write-Host("配列：" + $array1)

$target = 26
Write-Host("検索値：" + $target)

$result = linearSearch $array1 $target
Write-Host ("結果：" + $result)

Read-Host

実行

実行は右クリックメニューの「PowerShellで実行」をクリックします。

配列の中で26が格納されている位置は、7番目であることが分かりました。 ※配列は0から数えることに注意

バイナリサーチ

次はバイナリサーチです。

日本語名の二分探索の通り、真ん中のデータを見て検索値と違うほうの半分のデータを切り捨てる操作を繰り返します。

バイナリサーチで使用するデータはソート済であることが前提です。

ソースコード

実際に検索する部分をbinarySearch関数として切り離しています。

検索データの配列と見つけたい値を、引数としてbinarySearch関数に渡して実行します。

binarySearch.ps1

# search function
function binarySearch([array]$data, [int]$target){

    $head = 0
    $tail = $data.Length -1

    while($head -le $tail){
        $middle = [Math]::Floor( ($head + $tail) / 2 )
        
        if($data[$middle] -eq $target){
            # 位置検出、終了
            return $middle
        }

        # 検索位置の変更
        if($data[$middle] -lt $target){
            $head = $middle + 1
        }else{
            $tail = $middle - 1
        }

    }
    return -1
}

#position= (0, 1, 2, 3, 4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,  15)
$array1 = @(0, 1, 2, 4, 5, 15, 23, 26, 30, 31, 33, 35, 50, 75, 99, 100)

Write-Host("配列：" + $array1)

$target = 15
Write-Host("検索値：" + $target)

$result = binarySearch $array1 $target
Write-Host ("結果：" + $result)

Read-Host