スライド 1

アルゴリズムとデータ構造
補足資料4-2
「線形探索」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
void search( int x )
仮引数 int x
（自動）変数 int i
false
0
i != 10
&&
a[i] != x
true
i++;
true
i != 10
false
有
無
戻り値なし（void）
search( 3 )
仮引数 int x
3
（自動）変数 int i
false
0
i != 10
&&
a[i] != x
true
i++;
true
i != 10
false
有
無
戻り値なし（void）
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=0
search( 3 )
3
（自動）変数 int i
0
0 != 10
&&
a[0] != x
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → false
仮引数 int x
false
a[0]
i != 10
false
有
無
戻り値なし（void）
i=0
search( 3 )
3
（自動）変数 int i
0
0 != 10 true
&&
a[0] != x false
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → false
仮引数 int x
false
a[0]
i != 10
false
有
無
戻り値なし（void）
i=0
search( 3 )
3
（自動）変数 int i
0
0 != 10 true
&&
a[0] != x false
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → false
仮引数 int x
false
a[0]
0 != 10
false
有
無
戻り値なし（void）
search( 5 )
仮引数 int x
5
（自動）変数 int i
false
0
i != 10
&&
a[i] != x
true
i++;
true
i != 10
false
有
無
戻り値なし（void）
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=0
search( 5 )
5
（自動）変数 int i
0
0 != 10
&&
a[0] != x
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → true
仮引数 int x
false
a[0]
i != 10
false
有
無
戻り値なし（void）
i=0
search( 3 )
5
（自動）変数 int i
0
0 != 10 true
&&
a[0] != x true
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → true
仮引数 int x
false
a[0]
i != 10
false
有
無
戻り値なし（void）
i=0
search( 3 )
仮引数 int x
5
（自動）変数 int i
false
1
i != 10
&&
a[i] != x
true
i++;
true
i != 10
false
有
無
戻り値なし（void）
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=1
search( 5 )
5
（自動）変数 int i
1
1 != 10
&&
a[1] != x
true
i++;
true
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
!= → true
仮引数 int x
false
a[0]
i != 10
false
有
無
戻り値なし（void）
i=1
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=2
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=3
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=4
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=5
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=6
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
==
仮引数 int x
5
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
==
i==6 にあった！
「5: みつかりました」
i=0
search( 30 )
仮引数 int x
30
（自動）変数 int i
false
0
i != 10
&&
a[i] != x
true
i++;
true
i != 10
false
有
無
戻り値なし（void）
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=1
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=2
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=3
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=4
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=5
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=6
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=7
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=8
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
i=9
仮引数 int x
30
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
仮引数 int x
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
3
54
16
8
9
1
5
22
19
60
30
i==10
（参照データなし！）
→「30: みつかりませんでした」

Download Report