ITパスポート｜2分探索と線形探索の違いをやさしく解説

※ 本記事にはアフィリエイトリンク（PR）を含みます。

線形探索法とは、1件目から順に見ていくやり方のこと。2分探索法とは、まん中の1件と比べて、目当ての値がない側をまるごと捨てていくやり方のことです。そして先にお伝えしておくと、2分探索法のほうがいつでも速い、とは限りません。

「さがす」。ただそれだけのことに、どうしてわざわざ名前の付いたやり方が2つもあるのでしょうか。しかも参考書を開くと、片方には「速い」と書いてある。なら、速いほうだけ覚えれば済むのでは、と思いますよね。わかります。

ところが、その「速いほう」がいつでも速いわけではないということを、試験を作っている側が、公開されている問題ではっきり示していました。この記事は、そこまで含めて1本で見わたすために書きました。

この記事でわかること

• 線形探索法と2分探索法が、それぞれどう動いているのかが、15件のデータで最後まで追えるようになります

• 100万件のデータでも、2分探索法なら何回で見つかるのかが、具体的な数字で分かります

• どんなときに線形探索法のほうが少ない手間で終わるのか、そしてその根拠がどこにあるのかが分かります

この記事の要点（先に結論！）

• 線形探索法とは、データを1件目から順に見ていき、目当ての値かどうかを1つずつ確かめていく探し方のことです。

• 2分探索法とは、まん中の1件と比べて、目当ての値がない側をまるごと捨てる、これをくり返す探し方のことです。

• 2分探索法なら、100万件のデータの中からでも、いちばん手間がかかったときで20回くらべるだけで目当ての1件にたどりつけます（線形探索法なら、いちばん手間がかかったときで100万回です）。

• 2分探索法を使うには、データが小さい順（または大きい順）に並んでいる必要があります。線形探索法には、その条件がありません。

• 探す値がいちばん前にあるときは、線形探索法なら1回で終わります。同じデータなら探す値がどれであっても2分探索法のほうが手間が少ない、という趣旨の記述は、令和5年度の公開問題では誤りの選択肢として置かれていました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

1. 探索とは？　やり方に名前が付いているのは2つ

1.1 「さがす」という作業に、名前を付けたもの

まず、言葉から片づけてしまいましょう。探索とは、たくさんのデータの中から、目当ての1件を見つけ出すことです。

そして、その見つけ出し方の手順のことを、アルゴリズム（決まったやり方で答えにたどりつくための、手順の決めごと）と呼びます。探索アルゴリズムといえば、「さがすための手順」のことですね。

この記事では、データが配列（番号のついた入れ物が、一列に並んだもの）に入っているものとして話を進めます。この記事では、いちばん前を1番として数えます。その入れ物1つ1つに入っているデータを要素、その個数を要素数といいます。むずかしく考えなくて大丈夫です。一列に並んだデータと、その件数、という理解で最後まで読めますよ。

1.2 用語例に、そのままの名前で並んでいる

ここで、めずらしくうれしいお知らせがあります。この記事で扱う2つの言葉は、どちらも試験の範囲にそのままの名前で載っています。

ITパスポート試験のシラバスVer.6.5（シラバスとは、試験に出る範囲を示した一覧表のことで、Ver.6.5はその最新の版です）の小分類37(3)「代表的なアルゴリズム」の用語例に、探索のアルゴリズムとして次の2つが並んでいました（2026年7月時点）。

• 線形探索法

• 2分探索法

同じ用語例には、整列（ソート／並べ替え）のアルゴリズムも並んでいますが、そちらはこの記事では扱いません。この記事は、探索の2つだけを最後まで追いかけます。

なお、表記についてひとことだけ。シラバスでも公開されている問題でも、書き方は算用数字の「2分探索法」です（2026年7月時点）。参考書やWebの解説では「二分探索」と漢字で書かれることもありますが、指しているものは同じですよ。この記事は、試験の画面で戸惑わないように「2分探索法」で通します。

2. 線形探索法：1件目から、順に見ていく

2.1 やっていることは、それだけ

1つ目は線形探索法です。動きは、名前よりずっと単純です。1件目を見て、目当ての値かどうかを確かめる。違ったら2件目、また違ったら3件目。見つかったところで終わりで、最後まで行っても無ければ、「このデータの中には無い」と分かります。

たとえるなら、下駄箱です。端の1つを開けてみて、違ったら次の1つ。また違ったら、その次。開ける順番を工夫したりはしませんよね。あの動きが、そのまま線形探索法です。

ここで、この記事で最後まで使う言葉を1つ決めておきます。目当ての値と同じかどうかを見比べることを、この記事では「照合」と呼びます。1件見比べたら、照合1回です。

2.2 15件のデータで、実際に数えてみる

では、1から15までの数が、小さい順に一列に並んでいるとしましょう。ここから11を探します。

線形探索法なら、こうなります。

• 1を見て、違う。2を見て、違う。3を見て、違う……

• 11にたどりついたところで、見つかりました

• ここまでの照合は、11回です

つまり、探す値が何番目にあるかが、そのまま照合の回数になるんですね。いちばん後ろにある値なら15回、そこに無ければ15回照合して「無い」と分かります。

そして、線形探索法にはうれしい特徴が1つあります。

• データが並べ替えてあってもなくても、そのまま使えます

順番はどうでもいいんです。端から全部見るのですから、並んでいようがバラバラだろうが関係ありません。必ず見つかります。ただし、件数がふえるほど、そのぶんだけ手間もふえていきます。

3. 2分探索法：まん中と比べて、反対側を捨てる

3.1 主役の動きは「絞る」より「捨てる」

2つ目が2分探索法です。こちらは、少しだけ賢い動き方をします。まん中の1件と照合して、目当ての値がどちら側にあるかを決める。そして、無いと分かったほうを、まるごと捨てる。これをくり返します。

たとえるなら、辞書です。だいたいまん中のあたりを開いて、目当ての語より後ろが出てきたら、そこから先は、もう見なくていいと分かりますよね。あの「見なくていい」を作り出しているのが、2分探索法です。

大事なのは、絞り込むことそのものより、「見なくてよい件数」が消えていくことです。1回照合するたびに、残っていたうちの半分が、丸ごと見なくてよくなります。

3.2 まん中は、毎回動く

ここが、いちばんつまずきやすいところなので、先に言ってしまいますね。「まん中」は、ずっと同じ場所ではありません。

• 1回目のまん中は、全体のまん中です

• 2回目のまん中は、残った半分のまん中です

• 3回目のまん中は、さらに残った半分のまん中です

範囲そのものが縮んでいくので、そのたびにまん中も動く。ここが見えると、あとは同じ動きのくり返しだと分かります。

3.3 同じ15件で、同じ11を探してみる

さきほどと同じ、1から15までが小さい順に並んだデータです。探すのも同じ11にしましょう。

• 1回目……まん中は8。11は8より大きいので、1から8までをまるごと捨てます。残りは9から15の7件

• 2回目……残った7件のまん中は12。11は12より小さいので、12から15を捨てます。残りは9から11の3件

• 3回目……3件のまん中は10。11は10より大きいので、9と10を捨てます。残りは11だけ

• 4回目……11と照合して、見つかりました

照合は、4回でした。線形探索法では11回だったのですから、たしかに手間は減っています。

捨てた件数を見てください。1回目で8件、2回目で4件、3回目で2件。照合1回につき、見なくてよい件数がごっそり消えていくのが、この方法のしくみです。

4. 何回で見つかるのか、数えてみる

4.1 その前に、「どの場合の話か」をそろえる

回数の話をするときは、どの場合の話をしているのかをはっきりさせないと、かみ合わなくなります。見かたは3つあります。

• いちばん良い場合……いちばん運がよかったとき（1回目の照合で当たったとき）

• 最悪の場合……いちばん手間がかかったとき（最後まで見つからない位置にあったとき、またはデータの中に無かったとき）

• 平均……いろいろな値を探したときを、ならしたとき

これから出す数字は、ことわりがないかぎり「最悪の場合」の回数です。ここだけ覚えておいてくださいね。

4.2 件数をふやして、並べてみる

では、件数を大きくしていきましょう。線形探索法は最悪でその件数ぶん、2分探索法は最悪で次の回数になります。

• 15件……線形探索法は15回、2分探索法は4回

• 100件……線形探索法は100回、2分探索法は7回

• 100万件……線形探索法は100万回、2分探索法は20回

• 10億件……線形探索法は10億回、2分探索法は30回

100万件で20回。ここは、少し立ち止まる価値があります。100万回と20回では、もう比べるという感じがしませんよね。

そして、もっとおもしろいのはここから先です。100万件が10億件になっても、2分探索法の照合はたった10回しかふえません。件数が1,000倍になったのに、ふえたのは10回だけ。一方、線形探索法は、100万回が10億回へ、まっすぐ1,000倍になります。

理由は単純です。照合が1回ふえるごとに、探せる件数が2倍になるからなんですね。だから件数のほうがどれだけ大きくなっても、回数のほうはゆっくりとしか増えません。

4.3 線形探索法は、件数にそのまま比例する

一方、線形探索法はとても素直です。件数が10倍になれば、最悪の照合回数も10倍になります。1件ずつ見ているのですから、当然ですよね。

この「素直さ」は、実は試験の側でも問われたことがあります。令和5年度の公開問題 問69では、線形探索法にかかる計算量が、探す対象の配列の要素数に比例する、という趣旨の記述が正解でした（出典：令和5年度 ITパスポート試験 公開問題 問69）。

ここで計算量という言葉が出てきました。これは、処理にどれだけ手間がかかるかの見積もりのことです。この記事でずっと数えてきた「照合の回数」も、その見積もりの1つだと思ってください。

4.4 この回数は、計算できなくて大丈夫

大事なことを、正直に書いておきますね。いま出した回数を、自分で計算できるようになる必要はありません。

確認した令和3年度から令和8年度までの公開問題の中に、探索の回数を計算させるものは見当たりませんでした（2026年7月時点）。令和5年度 問69 が問うたのも、「要素数に比例する」という、言葉のレベルまでです。

ですからここは、「そんなに違うのか」と驚いていただければ、それでじゅうぶんです。持ち帰るのは、次の2つの言い方だけでいきましょう。

• 照合が1回ふえるごとに、探せる件数は2倍になる

• 件数が1,000倍になっても、ふえる照合は10回だけ

5. 速い方法が、いつでも速いとは限らない

5.1 ここまでの話には、続きがある

さて、ここまで読むと、「じゃあ2分探索法を使えばいいのでは」と思いますよね。ところが、ここに落とし穴があります。さっき出した数字は、ぜんぶ「最悪の場合」のものでした。では、いちばん良い場合はどうでしょうか。

思い出してください。線形探索法は、1件目から順に見ていく方法でした。ということは、探す値がいちばん前にあったら、1回目の照合で当たりです。

下駄箱でいえば、端の1つを開けたら、たまたまそれが目当てのものだった、ということですね。そのときは、それ以上さがす必要がありません。

5.2 同じ15件でも、勝ち負けが入れかわる

くらべてみましょう。データは、これまでと同じ1から15までが小さい順に並んだものです。

探す値が「1」（いちばん前）のとき

• 線形探索法……1回。1件目を見たら、もう当たりです

• 2分探索法……4回。まん中の8から始めるので、いちばん前にたどりつくまでに、4回かかります

探す値が「15」（いちばん後ろ）のとき

• 線形探索法……15回。端から順なので、最後まで行きます

• 2分探索法……4回。こちらは変わりません

同じデータなのに、勝ち負けが入れかわりました。探す値がどこにあるかで、少ない照合で済むほうが変わってしまうんですね。

5.3 これは、試験の側もそう見ている

「そんな細かい話、試験には関係ないのでは」と思われるかもしれません。ところが、ここがこの記事でいちばんお伝えしたいところなんです。

令和5年度の公開問題 問69には、こんな趣旨の記述が置かれていました。同じ配列を使うなら、探す値がどれであっても2分探索法のほうが計算量が少ない、という内容です。そして、この記述は選ぶべきでない側にありました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

つまり、試験を作っている側が、「探す値によっては、線形探索法のほうが少ない手間で終わることがある」という立場に立っているわけですね。

この記事の合言葉は、これです。

• 速い方法が、いつでも速いとは限らない

大事なのは、どちらが速いかを覚えることではなく、いつ速いのかを知ることです。そう考えると、2つのやり方が並んで用語例に載っている理由も、少し見えてきませんか。

6. 2分探索法の条件：小さい順に並んでいること

6.1 並んでいないと、どうなるのか

2分探索法には、使うための条件が1つあります。

• データが、小さい順（または大きい順）に並んでいること

小さい順に並んでいることを昇順、大きい順に並んでいることを降順といいます。どちらでもかまいませんが、並んでいること自体は、どうしても必要です。なぜでしょうか。理由は、2分探索法が何をしているかを思い出すと分かります。

2分探索法は、まん中と照合した結果だけを頼りに、片側をまるごと捨てています。「まん中より小さいのだから、後ろ側にあるはずがない」という判断ですね。

この判断が成り立つのは、データが順番に並んでいるときだけです。バラバラに並んだデータで同じことをすると、どうなるか。捨てたほうに目当ての値が入っていても、二度と見に行きません。結果として、あるはずの値を「無い」と答えてしまうんですね。

「使えません」ではなく、「見落とします」。こちらのほうが、条件の重さが伝わると思います。

6.2 この条件は、入れかえて出されたことがある

そして、この条件がどちらに付くのかは、実際の公開問題で試されています。

令和5年度の公開問題 問69には、この条件を線形探索法のほうに付け替えた記述が置かれていました。線形探索法を使うには配列が昇順または降順に並んでいる必要がある、という内容です。そして、この記述も選ぶべきでない側にありました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

条件が付くのは2分探索法のほう。線形探索法には付きません。入れかえて置かれることがある、と知っておくだけで、読み間違えにくくなりますよ。

7. 並べ替えるコストを払ってでも得なのは、どんなとき？

7.1 並べ替えという作業にも、手間はかかる

ここまでで、1つ疑問が残っているはずです。「では、その並べ替えは、だれがいつやるのでしょうか。」

データは、はじめから都合よく並んでいるとはかぎりません。並べ替えるなら、その作業そのものにも手間がかかります。データを決まった順に並べ替えることを、整列（ソート／並べ替え）といいます。

どれくらい手間がかかるものなのか。それが見える公開問題があります。令和7年度の公開問題 問98は、4件のデータを昇順（小さい順）に整列（ソート／並べ替え）するとき、示された手順が何回実行されるかを数えさせる問題でした。答えは4回です（出典：令和7年度 ITパスポート試験 公開問題 問98）。

たった4件でも、手順は4回動いています。並べ替えはタダではない、ということですね。

7.2 1回だけ探すのか、何度もくり返し探すのか

そこで、探す回数のほうに目を向けてみましょう。

• これから1回しか探さないなら……並べ替える手間のほうが、大きくなってしまうことがあります

• 同じデータを、これから何度もくり返し探すなら……最初に1回だけ並べ替えておけば、そのあとの探索は、ずっと軽くなります

下駄箱でいえば、先に名前順のラベルを貼り直しておくようなものですね。1回さがすだけなら、貼り直している間に見つかってしまいます。でも、毎日さがすのなら、最初の1回の手間は取り返せます。

ひとつ、正直に断っておきますね。この節の話には、シラバスや公開問題のうらづけがありません。ここまでに出てきた用語の意味を組み合わせれば導ける範囲の話だと受け取ってください。覚える対象ではなく、「なるほど」で通り過ぎていただいてかまいません。

8. 試験ではどこまで？　ここから先は追いかけなくて大丈夫

8.1 3つのグループに分けておく

最後に、勉強の範囲をはっきりさせておきます。やらなくていいことが決まると、気持ちが軽くなりますよ。この記事に出てきた言葉を、3つに分けてみます。

(1) 用語例に、そのまま並んでいる言葉

• 線形探索法／2分探索法（シラバスVer.6.5 小分類37(3)。2026年7月時点）

(2) 用語例には並んでいないけれど、公開されている問題に実際に使われていた言葉

• 計算量／昇順／降順／要素／要素数（いずれも令和5年度 ITパスポート試験 公開問題 問69 に登場。2026年7月時点）

(3) 用語例にも、確認した公開問題にも、見当たらなかったもの

• 計算量を記号で書き表す方法。この記事では扱いませんでした（2026年7月時点）

ここで、線を1本引いておきます。わたしが目で確かめたのは、シラバスの印刷ページ36〜39です。ですから書けるのは「小分類36〜39の用語例には並んでいません」までであって、「シラバスのどこにもありません」とは書けません。

8.2 追いかけなくていいことを、決めておく

そのうえで、この記事の範囲では追いかけなくていいことを並べておきますね。

• 回数を自分で計算できるようになる必要はありません。 確認した令和3年度から令和8年度までの公開問題に、探索の回数を計算させるものは見当たりませんでした（2026年7月時点）

• 記号を使った書き表し方も、この記事では扱いません。用語例にも、確認した公開問題にも見当たらなかったからです

• プログラムを書けるようになる必要もありません。 ただし理由は「プログラムが出ないから」ではありません。試験で使われるのは擬似言語（ITパスポートの試験で使われる、試験専用の書き方）のほうだからです。実際、令和8年度の公開問題 問67 は、擬似言語で書かれた並べ替えの処理を読ませる問題でした（出典：令和8年度 ITパスポート試験 公開問題 問67）

• 小分類37には、【活用例】の枠がありません（2026年7月時点）。手を動かして作る形では求められていない、と読める書きぶりです

なお、擬似言語を読むときに1つだけ注意があります。令和8年度 問67 の問題文には、配列の要素番号が1から始まると書かれていました（出典：同問）。参考書で使われるプログラム言語には、0から数えるものもありますので、行き来するときは、そこだけ気にしておくと混乱しません。ITパスポートの試験では1から数える、と押さえておけば大丈夫ですよ。

8.3 出題の実績は、正直にここまで

最後に、いちばん誠実な線引きをしておきます。

この記事で出典を示せる出題例は、令和5年度 問69・令和7年度 問98・令和8年度 問67 の3問です。そして出題数や配点は公表されていません（2026年7月時点）ので、「必ず出ます」とも「もう出ません」とも書けません。

言えるのは、公開されている問題で、実際にこう問われたことがあるという事実まで。そのうえで、探す値がどれであっても2分探索法のほうが手間が少ない、という趣旨の記述を、令和5年度 問69 が選ばせなかった。ここが、この記事でいちばん持ち帰っていただきたい事実です。

9. まとめ：3行でふりかえり

1. 線形探索法は1件目から順に見ていくやり方、2分探索法はまん中と比べて反対側をまるごと捨てるやり方です。

2. 2分探索法なら、最悪の場合でも100万件で20回、10億件でも30回。照合が1回ふえるごとに、探せる件数は2倍になります。

3. ただし、探す値がいちばん前にあれば線形探索法は1回で終わります。速い方法が、いつでも速いとは限りません。

いかがでしたか？　探索という言葉が、「速いほう・遅いほう」の2択ではなくなったのではないでしょうか。どちらにも得意な場面があって、条件が付くのは片方だけ。そこまで見えていれば、この単元はもう自分のものですよ。

10. よくある質問（FAQ）

Q1. 線形探索法と2分探索法の違いは何ですか？

A. 探し方と、使うための条件が違います。 線形探索法は、1件目から順に、目当ての値かどうかを1つずつ見ていく方法で、データが並べ替えてあってもなくても使えます。一方、2分探索法は、まん中の1件と見比べて、目当ての値がない側をまるごと捨てる、これをくり返す方法です。こちらは、データが昇順（小さい順）または降順（大きい順）に並んでいることが条件になります。手間の面では、件数が多いほど2分探索法が有利ですが、探す値がいちばん前にある場合は、線形探索法が1回で終わります。

Q2. 2分探索法なら、100万件のデータは何回で見つかりますか？

A. いちばん手間がかかった場合で、20回です（見比べる回数を数えた場合）。件数が10億件にふえても、30回で足ります。理由は、1回見比べるごとに、探せる件数が2倍になっていくからです。だから件数が1,000倍になっても、ふえる回数は10回だけで済みます。ちなみに線形探索法なら、100万件の中でいちばん手間がかかった場合は100万回です。なお、この回数を自分で計算できるようになる必要はありません。確認した令和3年度から令和8年度までの公開問題に、探索の回数を計算させるものは見当たりませんでした（2026年7月時点）。

Q3. 2分探索法を使うには、なぜ並べ替えが必要なのですか？

A. 並んでいないと、目当ての値を見落としてしまうからです。2分探索法は、まん中の1件と見比べた結果だけを頼りに、「こちら側にあるはずがない」と決めて片側をまるごと捨てます。この判断が成り立つのは、データが小さい順（または大きい順）に並んでいるときだけなんですね。バラバラに並んだデータで同じことをすると、捨てたほうに目当ての値が入っていても、二度と見に行きません。結果として、あるはずの値を「無い」と答えてしまいます。なお、この条件を線形探索法のほうに付け替えた記述が、令和5年度の公開問題では選ぶべきでない側に置かれていました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

Q4. 線形探索法のほうが速くなることはありますか？

A. あります。探す値がいちばん前にあるときです。 線形探索法は1件目から順に見ていくので、目当ての値が1件目にあれば、1回で終わります。一方、2分探索法は、まん中から見にいく方法なので、いちばん前の値にたどりつくまでには何回かかかります。たとえば1から15までが小さい順に並んだデータで「1」を探すと、線形探索法は1回、2分探索法は4回です。実際、同じ配列なら探す値がどれであっても2分探索法のほうが計算量（処理にどれだけ手間がかかるかの見積もり）が少ない、という趣旨の記述が、令和5年度の公開問題では選ぶべきでない側に置かれていました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

Q5. 「2分探索」と「二分探索」は同じものですか？

A. 同じものです。 指しているやり方に違いはありません。ただし、ITパスポート試験のシラバスVer.6.5と、公開されている問題では、算用数字の「2分探索法」と書かれています（2026年7月時点）。参考書やWebの解説では「二分探索」と漢字で書かれることも多いので、どちらを見ても同じものだと思って読んで大丈夫ですよ。試験の画面で戸惑わないよう、覚えるときは「2分探索法」の形にしておくのがおすすめです。

おすすめ教材（PR）

探索は、手を動かして1回追いかけてしまえば、二度と忘れないところです。この記事のように、15件くらいの小さなデータで自分の手で数えてみると、参考書の説明が急に読める文になりますよ。

ITパスポートの公開問題は公式サイトや無料サイトでも解けますから、参考書は必ずしも必須ではありません。

それでも1冊ほしいなら、このシリーズと並走できる、こちらがおすすめです。本で探すときは、目次の「アルゴリズム」のあたりを見てみてくださいね。

『【令和8年度】いちばんやさしいITパスポート 絶対合格の教科書＋出る順問題集』

章立てがシリーズ全体と対応しているので、記事と本を行き来しながら進めやすい1冊です（2026年7月時点）。くり返しますが、これがなくても合格はできます。でも、あると近道になりますよ。

次に読む

探索は、「アルゴリズム」という大きな単元の一部です。順次・選択・繰返しの3つの基本構造や、擬似言語の読み方まで見わたしたくなったら、本拠地へどうぞ。この記事は全文無料です。

【この分野の本拠地】ITパスポート｜アルゴリズムとは？擬似言語をやさしく解説

【上の記事の確認問題（無料）】

【前の記事】オブジェクト指向とクラス／インスタンスはこちら。

【次の記事】次は、CPUの中身です。

【もっと問題を解きたい人へ】テクノロジ系 予想問題集

シリーズの目次：ITパスポートの出題範囲 全体地図

この記事を書いた人
simic（IT資格ノート）。文系・非エンジニアの視点で、つまずきやすいIT用語を「たとえ」でかみくだきながら、資格の勉強ノートを書いています。→ くわしい自己紹介：https://note.com/simic_0531/n/n5ed7f56f1ab9

最終更新：2026年7月

Amazonのアソシエイトとして、simic（IT資格ノート）は適格販売により収入を得ています。

この先にあるのは、オリジナルの練習問題6問です。中身は、探す値がどこにあるかで変わる回数・100万件での照合回数・件数が2倍になる話・並べ替えの条件・くり返し探す場合・件数に比例する話。どれも、この記事で読んだことだけで解けます。

11. 練習問題：6問で確かめる

すべてこの記事のオリジナル問題です。選択肢を見る前に、自分の言葉で答えを作ってみてください。

問1　探す値が、いちばん前にあったら

1から15までの数が小さい順に一列に並んだデータがある。この中から「1」を探すとき、少ない照合（目当ての値と同じかどうかを見比べること）で終わるのはどちらの方法か、正しい説明を選びなさい。

正解：ア

解き方

1. 線形探索法は、1件目から順に見ていく方法。探す値が1件目にあるなら、照合は1回で終わる

2. 2分探索法は、まん中から見にいく方法。いちばん前の値にたどりつくまで、この15件なら4回かかる

3. だからこの場合は、線形探索法のほうが少ない

ここがひっかけ
イは、まん中から見にいくことを「前に強い」と取り違えた説明ですね。まん中から見にいく方法は、いちばん前の値にはむしろ遠いんです。ウは「探す値によって回数は変わらない」という点が誤りです。エは逆で、線形探索法は並べ替えてあっても使えます。なお、同じ配列なら探す値がどれであっても2分探索法のほうが計算量が少ない、という趣旨の記述が、令和5年度の公開問題では選ぶべきでない側に置かれていました（出典：令和5年度 ITパスポート試験 公開問題 問69）。

問2　100万件を、2分探索法で

小さい順に並んだ100万件のデータの中から、目当ての1件を2分探索法で探す。いちばん手間がかかった場合の照合回数として、最も近いものはどれか。

正解：ア

解き方

1. 2分探索法は、1回照合するごとに、残りの半分がまるごと候補から外れる

2. 照合が1回ふえるごとに、探せる件数は2倍になる

3. その関係でいくと、100万件はおよそ20回。ちなみに10億件でも30回

ここがひっかけ
エの約50万回は、線形探索法で100万件を探したときの平均（ならしたときの回数）です。イとウは、2分探索法の手間を大きく見積もりすぎた数字ですね。100万という件数の大きさに引っぱられると、20回という答えが小さすぎるように感じてしまうんです。そこが、この問題のいちばんのひっかけどころですよ。

問3　照合が1回ふえると、どうなる？

2分探索法について、照合の回数を1回ふやしたときに探せる件数の変わり方として、適切なものはどれか。

正解：ア

解き方

1. 2分探索法は、1回照合するたびに、見なくてよい件数が半分ずつ消えていく方法

2. 逆から見れば、照合を1回ふやすたびに、扱える件数は2倍になるということ

3. だから、件数が大きくなっても、回数のほうはゆっくりとしかふえない

ここがひっかけ
イを選びたくなるのは、線形探索法の感覚が残っているときですね。1件ずつ見ていく線形探索法なら、1回ふえて1件ふえるで正しいのですが、2分探索法はそこが違います。ウの10倍は、件数と回数の関係を大きく取りすぎです。この「2倍」を持っておくと、100万件で20回という数字が、丸暗記ではなくなりますよ。

問4　条件が付くのは、どちらか

線形探索法と2分探索法について、データが昇順（小さい順）または降順（大きい順）に並んでいることが必要なのはどちらか。適切な説明を選びなさい。

正解：ア

解き方

1. 2分探索法は、まん中と照合した結果だけを頼りに、片側をまるごと捨てる

2. その判断が成り立つのは、データが順番に並んでいるときだけ

3. 一方、線形探索法は端から全部見るので、並び方は関係ない

ここがひっかけ
イは、条件を反対側に付け替えた説明です。じつは、線形探索法を使うには配列が昇順または降順に並んでいる必要がある、という趣旨の記述が、令和5年度の公開問題では選ぶべきでない側に置かれていました（出典：令和5年度 ITパスポート試験 公開問題 問69）。入れかえて置かれることがあるので、どちらに条件が付くのかは、はっきりさせておきましょう。条件が付くのは2分探索法のほうです。

問5　これから何度も探すなら

バラバラに並んだデータがある。このデータの中から、これから何度もくり返し目当ての1件を探すことになった。先にデータを小さい順に並べ替えておく意味の説明として、最も適切なものはどれか。

正解：ア

解き方

1. 2分探索法を使うには、小さい順（または大きい順）に並んでいることが条件

2. 並べ替えの作業そのものにも、手間はかかる

3. だから、これから何度もくり返し探すなら、最初の1回の手間を取り返せる

ここがひっかけ
イは言いすぎですね。並べ替えても、目当ての値と見比べる作業そのものは無くなりません。ウは「手間がかからない」という点が誤りです。令和7年度の公開問題 問98では、4件を昇順に整列（ソート／並べ替え）するのに、示された手順が4回実行されるという形で、その手間が問われていました（出典：令和7年度 ITパスポート試験 公開問題 問98）。エは、1回で見つかるのは運がよかったときだけです。

問6　件数が10倍になったら

線形探索法で、データの件数が10倍になった。いちばん手間がかかった場合の照合回数は、どうなるか。

正解：ア

解き方

1. 線形探索法は、1件目から順に、1件ずつ見ていく方法

2. いちばん手間がかかるのは、最後まで見たとき。つまり件数ぶんの照合になる

3. だから件数が10倍になれば、回数もそのまま10倍

ここがひっかけ
イとエは、2分探索法の感覚が混ざったときに選んでしまう選択肢ですね。照合が1回ふえるごとに件数が2倍になるのは、2分探索法のほうです。この素直さは試験でも問われていて、令和5年度の公開問題 問69では、線形探索法にかかる計算量が探す対象の配列の要素数に比例する、という趣旨の記述が正解でした（出典：令和5年度 ITパスポート試験 公開問題 問69）。「比例する」とは、件数が10倍になれば回数も10倍になる、ということなんですね。