特典

Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

割引を受け取る
トラック
/
Delphi Pascal
Delphi Pascal
/
演習
/
二分探索
二分探索

二分探索

初級
概要コミュニティの解答

はじめに

数学者であり、シンガーソングライターでもある人たちのグループに、偶然出会いました。彼らは、お気に入りの数それぞれのために歌を書いています。そして、ご想像のとおり、お気に入りの数はたくさんあります（0や73、6174など）。

お気に入りの数の歌を聴いてみたくなりましたが、あまりに多くの歌を聴き進めなければならないので、目当ての歌を見つけるにはしばらく時間がかかりそうです。幸いなことに、彼らは歌をプレイリストにまとめ、タイトル順に並べています。タイトルとは、その歌が歌っている数そのものです。

タイトルさえわかっていれば、二分探索アルゴリズムを使って歌をすばやく見つけられることに気づきます。

説明

ここでの課題は、二分探索アルゴリズムを実装することです。

二分探索アルゴリズムは、配列を繰り返し半分に分割し、探している要素を含む半分だけを残すことで、配列の中から目的の要素を見つけ出します。 これにより、目的の要素を見つけるまで、あるいは候補となる場所がすべてなくなるまで、その要素があり得る場所をすばやく絞り込んでいけます。

Caution

二分探索は、配列がソートされている場合にのみ機能します。

アルゴリズムは次のようになります。

  • ソートされた配列の真ん中の要素を見つけ、それを探している要素と比較します。
  • 真ん中の要素が探している要素であれば、それで完了です！
  • 真ん中の要素が探している要素より大きければ、その要素と、それより後ろにある要素をすべて除外できます。
  • 真ん中の要素が探している要素より小さければ、その要素と、それより前にある要素をすべて除外できます。
  • 配列の要素がすべて除外されたなら、探している要素は配列の中にありません。
  • そうでなければ、除外されていない部分に対して同じ処理を繰り返します。

例を見てみましょう。

次のようにソートされた配列[4, 8, 12, 16, 23, 28, 32]から、数値23を探すとします。

  • まず、23を真ん中の要素である16と比較します。
  • 23は16より大きいので、配列の左半分を除外でき、[23, 28, 32]が残ります。
  • 次に、23を新たな真ん中の要素である28と比較します。
  • 23は28より小さいので、配列の右半分を除外でき、[23]が残ります。
  • 目的の要素が見つかりました。

出典

Wikipediaリンクは新しいウィンドウまたはタブで開きます
GitHubで編集する リンクは新しいウィンドウまたはタブで開きます
Delphi Pascal Exercism

二分探索を始める準備はできましたか？

Exercismに登録すれば、76個の演習、そして本物の人間によるメンタリングとともに、Delphi Pascalを学んでマスターできます。すべて無料です。

登録は無料です！ Exercismにログイン