線形探索(順次探索)

情報処理用語集

線形探索(順次探索)

情報処理関連の用語について、基本的知識を紹介しているサイトです。近年、情報処理はインターネットなどの普及により、毎日生活していく中で熟知され、さまざまなシーンで利用されており日常生活の一部になりつつあります。コンピュータ社会において、技術の急激な進歩や発展に伴い情報処理用語も大幅に増えてきております。膨大な量の用語を全てご紹介するのは難儀ではありますが、多様化する現状に対応して、基本的な用語から、コンピュータ全般、ソフトウェア、アルゴリズムとデータ構造、システム開発の基礎、ファイルとデータベース、通信ネットワーク、情報処理システム、産業社会と情報化、情報化の課題など、いろいろな観点から用語を努めて簡潔で、できる限り解りやすく、丁寧に説明させていただいております。情報処理関連用語の理解やスキルアップで多くの情報と知識を習得していただけたら幸いです。「初級上級システムアドミニストレータ」や「上級システムアドミニストレータ」、「基本情報技術者」、「特種情報処理技術者」、「ソフトウェア開発技術者」などIT技術関連の試験対策にも是非、お役立てください。情報処理用語集は情報処理技術者試験資格取得を目指すあなたを応援させていただきます。

線形探索(順次探索)


スポンサードリンク






情報処理用語集
TOP


A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 数字



スポンサードリンク







情報処理用語集>線形探索(順次探索)

linear search

線形探索順次探索)とは、データの集合の1番目から順々に比較して

虱潰しにデータを探索する方法のこと。


データが整列されている必要はないが、探索に時間がかかる。


これに対して、二等分探索は、データが整列していなければならないが、

探索の時間は順次探索より短くてすむ。

探索法 順次探索 二等分探索
データの並び ランダム可 昇順か降順に整列
平均探索回数 (N+1)÷2 ≦Nを満たす最大x
最大探索回数 N<2を満たす最小のy
イメージ図
上から順々に比較
←あった

中央値を比較
←中央値@
←あった
←中央値A


線形探索は、データ個数分ループして、データの先頭から虱潰しに

比較していくので、毎回、データの終わりに達したかどうかのチェックが

必要になる。

そこで、最後のデータの次に探索データと同じデータを番兵(sentinel)として

置いておけば、データのN個の中に探索データがなくても、N+1個目で

必ず見つかるので、データの終わりに達したかどうかを毎回チェックする必要が

なくなる。

番兵のことを番人とも呼び、ループの終了判定を間単位するために、

線形探索以外にも広く用いられている。




スポンサードリンク


Copyright (C) 情報処理用語集 All Rights Reserved