擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

探索のコードが出てくると、途端に何をしているか分からなくなる。

配列の中から目的の値を探すだけなのに、なぜこんなに複雑に見えるのでしょうか？

科目Bで出てくる探索の問題は、実は種類が多くありません。線形探索と二分探索、この二つの型を知っているだけで、初見のコードでも見当がつくようになります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、データを一件ずつ調べる処理と、並んでいることを前提に一気に絞り込む処理では、書き方も速さもまったく変わります。

その違いは、試験に出る擬似言語でもそのまま現れます。この記事では、二つの探索を並べながら、コードのどこを見れば見分けられるのかを整理していきます。

探索とは何をしている処理なのか¶

まずは言葉の意味を確認しておきましょう。探索とは、たくさんのデータの中から目的のものを見つけ出す処理です。

配列 {12, 5, 30, 8} の中から 30 を探して、それが3番目にあると答える。やっていることは、それだけです。

難しく見えるのは、探し方に工夫が入っているからです。工夫の中身が分かれば、コードは急に読みやすくなります。

そして探索の問題では、答えとして返すものが二通りあります。見つかったかどうかの真偽か、見つかった位置の添字か、どちらかです。

問題文の最初に、何を返す関数なのかが必ず書かれています。そこを読み飛ばさないでください。

探索の問題が科目Bで狙われる理由¶

探索は、ループと条件分岐と配列が全部入っています。基本の三つを一度に試せるので、出題側からすると都合がよいのです。

逆に言えば、探索が読めるようになると、他の問題も読めるようになります。学習の投資先としては効率がよい分野です。

配列の添字の数え方があやふやなままだと、探索のコードは必ず途中で分からなくなります。先に土台を固めておくと、この記事の内容もすっと入ってきます。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

線形探索は前から順に見ていくだけ¶

一つ目は線形探索です。名前は難しそうですが、やっていることは拍子抜けするほど単純です。

配列の先頭から順に、一つずつ目的の値と比べていきます。一致したらそこで終わり、最後まで無ければ見つからなかったと答えます。

人が本棚から一冊の本を探すとき、左から順に背表紙を見ていく。あの動きとまったく同じです。

実際のコードを見てみましょう。見つかった位置を返す関数の形です。

○整数型: senkeiTansaku(整数型の配列: data, 整数型: target)
  整数型: i

  for (i を 1 から data の要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      return i        /* 見つけたので、ここで終わる */
    endif
  endfor

  return -1           /* 最後まで無かった */

読むときは、二つの出口を先に確認してください。途中の return i と、末尾の return -1 です。

この関数から抜ける道は、その二本しかありません。出口が分かっていれば、途中の処理を追うのも楽になります。

見つかったら止める、という書き方¶

線形探索でいちばん大事なのは、見つかった時点で処理をやめるところです。ここを見落とすと、答えがずれます。

data が {12, 5, 30, 8} で target が 5 なら、i が 2 のときに return されます。3番目以降は一度も実行されません。

ではもし return を使わず、真偽を表す変数で管理したらどうなるでしょうか。次のような書き方も、試験ではよく出ます。

○論理型: fukumu(整数型の配列: data, 整数型: target)
  整数型: i
  論理型: mitsuketa ← false

  i ← 1
  while (i ≦ data の要素数 and mitsuketa = false)
    if (data[i] = target)
      mitsuketa ← true
    endif
    i ← i + 1
  endwhile

  return mitsuketa

こちらは while の条件に mitsuketa = false が入っているのがポイントです。見つかった瞬間に条件が偽になり、次の周回に入りません。

同じ線形探索でも、止め方が違うだけで見た目がかなり変わります。while と for の使い分けが不安なら、繰返しの基本から確認しておくと読み違えが減ります。

【関連記事】擬似言語のwhileとforってどう違う？繰返し処理で迷子にならない方法を詳しく解説

見つからなかったときの値に注意する¶

もう一つ、地味ですが差がつくところがあります。見つからなかったときに何を返すか、です。

添字を返す関数では、-1 や 0 を返す形がよく使われます。配列の添字として存在しない値を選んで、見つからなかったという意味に使っているのです。

問題によっては、要素数より大きい値を返す設計になっていることもあります。ここは問題文の指定が絶対なので、思い込みで決めないでください。

二分探索は半分ずつ捨てていく¶

二つ目は二分探索です。こちらは条件が一つ付きます。

配列があらかじめ小さい順、または大きい順に並んでいること。この前提が無ければ使えません。

並んでいるなら、真ん中を見ただけで答えが左右どちらにあるか分かります。だから毎回、半分を丸ごと捨てられるわけです。

辞書で単語を引くときに、だいたいの見当をつけて開きますよね。あの感覚に近い探し方です。

コードにすると、こうなります。

○整数型: nibunTansaku(整数型の配列: data, 整数型: target)
  整数型: lo ← 1
  整数型: hi ← data の要素数
  整数型: mid

  while (lo ≦ hi)
    mid ← (lo + hi) ÷ 2 の商    /* 中央の位置。小数は切り捨てる */

    if (data[mid] = target)
      return mid                /* 見つけた */
    elseif (data[mid] < target)
      lo ← mid + 1              /* 右半分に絞る */
    else
      hi ← mid - 1              /* 左半分に絞る */
    endif
  endwhile

  return -1

追うべき変数は lo と hi と mid の三つだけです。この三つが毎回どう動くかを見れば、処理の全体が見えます。

中央の求め方でつまずく¶

最初の関門は mid の計算です。(lo + hi) ÷ 2 の商、という書き方に慣れていない人が多いところです。

割り算の結果に小数が出たら、それを切り捨てて整数にします。lo が 1 で hi が 4 なら、mid は 2 です。

添字は整数でなければ配列を指せません。だから切り捨てが必要になる、と理解しておけば忘れません。

なお、切り捨ての書き方は問題によって違います。商という言葉を使う形もあれば、専用の関数が定義されている形もあるので、その問題の定義に従ってください。

探索範囲の更新は +1 と -1 を忘れない¶

二つ目の関門は、範囲の更新です。ここが二分探索でいちばん間違えやすいところだと感じています。

lo ← mid + 1 の +1 と、hi ← mid - 1 の -1。この二つを落とすと、同じ場所を延々と調べ続けます。

理由は単純で、mid の位置は既に調べ終わっているからです。もう一度含める必要がないので、一つ隣から次の範囲を始めます。

もし lo ← mid と書いてしまうと、範囲が縮まらなくなる場面が出てきます。すると while の条件がいつまでも真のままになり、処理が終わりません。

空欄補充で +1 か -1 かを選ばせる問題は、実際に出ます。理由まで押さえておくと、迷わず選べます。

実際に半分ずつ減る様子を見る¶

言葉だけでは実感しにくいので、動きを表にしてみましょう。data が {3, 8, 12, 20, 27, 31, 45} の7個で、target が 31 の場合です。

その前に、この配列が小さい順に並んでいることを確認してください。並んでいるからこそ、次の判断ができます。

7個の中から、たった2回で見つかりました。線形探索なら6回目でやっと見つかる位置です。

この差が、データが増えるほど広がっていきます。要素が1000個あっても、二分探索なら10回ほどで答えにたどり着きます。

こうした変数の動きを紙に書き出す作業は、探索以外の問題でも効きます。書き方の型を持っておくと、本番で慌てません。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

二つの探索を並べて整理する¶

ここまでの内容を、一度まとめて見比べてみましょう。違いがはっきりすると、問題を見た瞬間にどちらか判断できるようになります。

比べるポイントは、前提条件と速さ、そしてコードの見た目です。

表の一行目が、見分けの決め手です。問題文に整列済みと書かれていたら、二分探索を疑ってください。

逆に、並び順の記述がまったく無ければ線形探索です。ここだけで、コードを読む前から見当がつきます。

速いほうを常に選べばいいわけではない¶

こう並べると、二分探索のほうが優れているように見えます。ですが、いつでもそちらがよいとは限りません。

データが並んでいなければ、まず並べ替える必要があります。一度探すだけなら、並べ替えの手間のほうが大きくなることもあります。

私も実務で、件数が数十件と分かっている処理には、あえて単純な順次検索を書くことがあります。読みやすさが保守のしやすさに直結するからです。

試験では速さを問われますが、背景にはこうした使い分けがあります。知っておくと、選択肢の意図も読み取りやすくなります。

手を動かして確かめると定着が早い¶

読んで納得しても、自分で追うとまた違うところで詰まります。とくに二分探索は、lo と hi の動きを目で見ると理解が一段深まります。

Giji Academy の擬似言語シミュレーターでは、一行ずつ実行しながら変数の中身を確認できます。mid が切り捨てで求まる様子も、そのまま見えます。

自分の予想と実行結果を突き合わせて、ずれた場所を探してみてください。そこが、次に復習すべき一点です。よかったら学習ページから試してみてください。

よくある間違いと直し方¶

私が学習相談を受ける中で、探索の問題では同じつまずきが繰り返し出てきます。まとめて確認しておきましょう。

一番多いのは、三行目の切り捨てです。頭では分かっていても、手を動かすと 2.5 のまま進めてしまう人が少なくありません。

紙に書くときは、mid の欄に整数だけを書くと決めてしまいましょう。それだけで防げます。

科目Bは20問を100分で解く試験です。一問あたりに使える時間を考えると、探索の型を覚えているかどうかは大きな差になります。

コードの構造を先に見抜ければ、残りは値を追うだけです。その順番を守ってください。

まとめ¶

線形探索は、先頭から一つずつ比べていく素直な探し方でした。見つかった時点で止めるところが、読み取りの要になります。

二分探索は、並んでいることを前提に、中央を見て半分を捨てる探し方です。lo と hi と mid の三つを追えば、処理は必ず追えます。

見分け方は、問題文に整列の記述があるかどうか。この一点で判断できます。

範囲の更新に付いている +1 と -1 は、調べ済みの位置を外すためのものでした。理由が分かっていれば、空欄補充でも迷いません。

擬似言語の記号や書き方そのものに不安が残る場合は、早見表で全体を眺めておくと安心です。

【関連記事】擬似言語の記号・記述形式一覧｜試験前のチェック早見表

探索が読めるようになると、整列や集計の問題も同じ目線で読めるようになります。次に問題を開いたら、まず並び順の前提から探してみてください。