Commentsどうも!仙台ファクトリーのkouです。探索アルゴリズムと格闘した報告をしたいと思います。ような1万個の数値(乱数)の配列があります。数値に規則性はなく、最大で100万あります。目的の数値は100あり、その結果を以下のように出力します。要件:出来るだけ処理時間を短縮したいです。1万個の数値の中から目的となる100個の数値を素早く見つけるアルゴリズムを考えるというものだ。問題文を見てふと思ったこと与えられた1万個の乱数の配列が既に「昇順」に並んでいる→2分探索が使える目的の数値も並び替えれば探索が早くなる?(漠然と)2分探索については、前回の課題であるアルゴリズムとフローチャートについての調査でざっとやっただけでロジックの理解は曖昧な状態である。このロジックを考えることが今回の課題を解決する鍵になりそうだ。問題に取り掛かるが...*これ以降は、問題文の1万個の数値を『探索元データ』、100件の目的数値を『目的データ』と表記する。最初に考えたロジックが次の通りだ。array_n[100]探索元データの中央要素の添え字をmid探索元データの軸をjikuとする。*お気づきかもしれないが、jikuという意味不明な変数を用意してしまったのが、どハマリした原因である。探索元データの中央要素と目的データを比較データが一致したなら探索終了。array_[0])といった単純な比較を行っている。2分探索に理解のある人はここまでなら理解できるはず。2分探索は基本的にはこの繰り返しである。midの値を分岐に合わせて調整して比較していくということである。midが軸なのである。私はここで魔法の変数jikuを用意してしまった。これ以上、文章で解説するとややこしくなるのでコードで構造を示す。}}最初はmidを使い比較して2回目以降、midの値をjikuに移し比較している。if文の中の処理は省略しているが、ざっくり解説するとmidの値を半分にするmidの値をjikuに足し引きしているということを行っている。目的データとjikuを添え字とする探索元データの配列要素と比較を行い、目的データの値が大きい場合は、midの値をjikuに加算し、小さい場合は、midの値をjikuに減算している。この場合、終盤の細かい部分の探索が粗くなってしまう以下に出力結果の一例を示す。12345678910111213141516探索98回目5822の探索を始めますmidの値は2500jikuの値は7500midの値は1250jikuの値は6250midの値は625jikuの値は5625midの値は312jikuの値は5937midの値は156jikuの値は5781midの値は78jikuの値は5859midの値は39jikuの値は5820midの値は19jikuの値は5839midの値は9jikuの値は5830midの値は4jikuの値は5826midの値は2jikuの値は5824midの値は1jikuの値は5823midの値は0jikuの値は5823発見できませんでしたこのように範囲を絞りきる前に、midの値が0になってしまうことがあった。浮かばなかった件あと一歩のところで解決できそうな気がするのだが、これ以降前に進まなかった。あれこれ考えている内にあることに気づいてしまったのである。