線形探索法(リニアサーチ)について
線形探索法は、データ列の先頭から順番に調べて目的の要素を探すアルゴリズムです。
探索のイメージが一直線(linear)に探していく様子からリニアサーチと呼ばれています。
単純でわかりやすいアルゴリズムですが、探索の効率はよくありません。データ数が多くなればなるほど、後方部分の探索に時間がかかります。
線形探索法のイメージ
以下の図は線形探索法を使って探索値を探し出す様子のイメージです。
[線形探索法のイメージ]
サンプルコード
線形探索法のアルゴリズムを以下のプログラミング言語で紹介します。
- Tcl
- Python
サンプルコードについて
各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。
必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。
Tcl
[サンプル：linear-search.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 線形探索法(linear search:リニアサーチ)
# arr : 数値リスト
# n : 要素数
# i : 探索する要素の位置
# target : 探索値
array set arr {0 40 1 10 2 30 3 50 4 20}
set n [array size arr]
parray arr
puts -nonewline "探索値を入力する。: "
flush stdout
set target [gets stdin]
set i 0
while {$i < $n} {
if {$arr($i) == $target} {
puts "探索値: $target は0から数えて $i 番目にあります。"
exit
}
incr i
}
puts "探索値: $target は見つかりませんでした。"
[実行例]
$ ./linear-search.tcl arr(0) = 40 arr(1) = 10 arr(2) = 30 arr(3) = 50 arr(4) = 20 探索値を入力する。: 50 探索値: 50 は0から数えて 3 番目にあります。 $ ./linear-search.tcl arr(0) = 40 arr(1) = 10 arr(2) = 30 arr(3) = 50 arr(4) = 20 探索値を入力する。: 80 探索値: 80 は見つかりませんでした。
Python
[サンプル：linear-search.py]
#!/usr/bin/env python3
import sys
# 線形探索法(linear search:リニアサーチ)
# arr : 数値リスト
# n : 要素数
# i : 探索する要素の位置
# target : 探索値
arr = [40, 10, 30, 50, 20]
n = len(arr)
print(arr)
# 探索する値を入力
target = input('探索値を入力する。: ')
target = int(target) # 文字列から数値に変換
# 探索する(リニアサーチ)
i = 0
while i < n:
if arr[i] == target:
print(f'探索値: {target} は0から数えて {i} 番目にあります。')
sys.exit()
i += 1
print(f'探索値: {target} は見つかりませんでした。')
[実行例]
$ ./linear-search.py [40, 10, 30, 50, 20] 探索値を入力する。: 50 探索値: 50 は0から数えて 3 番目にあります。 $ ./linear-search.py [40, 10, 30, 50, 20] 探索値を入力する。: 80 探索値: 80 は見つかりませんでした。
コメント