どうも！仙台ファクトリーのkouです。 前回の続きで探索アルゴリズムと格闘した報告です。

それでは早速紹介していきます！

問題文(再掲）

以下のような１万個の数値（乱数）の配列があります。 １、３、６、１４、３４・・・・ 数値に規則性はなく、最大で１００万あります。 ただ、昇順になっています。 上記に対して目的の数値の検索をする処理をチャートで表してください 目的の数値は１００あり、その結果を以下のように出力します。 ５は３番目 ２５はありませんでした ４０００は４万番目

要件：出来るだけ処理時間を短縮したいです。

あることに気がついた件

魔法の変数jikuがすごく気になっていた。
どうして1回目はmidで比較して、2回目以降jikuで比較するのか。

そのことを疑問に感じていたとき、軸の計算がおかしいのではないかと思った。

そもそも軸、つまり探索元データの中央要素（の添え字）はどうやって決まっているのだろうか。これは

中央要素 = （最小の要素　＋　最大の要素）/ 2

で求められる。（前回のアルゴリズムを考えていたときに気がつかなかったのが恥ずかしい）

これに気づかなかったため、魔法のjikuを用意して手間のかかる処理を書いてしまった。

どうしてそれに気がついたか

問題文を見たときに気付いたもう1点。
目的の数値も並び替えれば探索が早くなる？（漠然と）

これについて考えていたとき、上司から次のアドバイスをいただいた。

目的の１００個の数値は「並んでいるかどうか書いていない」ので、これを昇順に並べ替えると目的の最大と最小がわかる

→目的の最小と最大が分かれば、探索元データはその範囲内に絞ることができる！
漠然と感じていた疑問が解けたと同時に上記のことに気がついた。

私が最初に考えたアルゴリズムでは、最初に『探索範囲の絞込み』を行っていなかったため、探索元データの最小と最大を「固定」にしたロジックになっている。（コードの中に最小と最大を表す変数が出てきてないのもそのためだ）つまり、最小要素と最大要素を見ていなかった。
探索元データの最小と最大が変われば中央の位置も変わる、ということに気がついたときもう少しシンプルなロジックにできるのではないかと思った。

ロジックを考え直す

ということで、ロジックを考え直した。

軸は最大要素と最小要素の和を半分にしたところに位置する

つまり、軸は自分で操作せずに最小要素と最大要素によって求めるということだ。（軸÷2はよくない）

これを前提にして、考えたコードが下記である。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

while(array_m[min] < array_m[max]) {
    mid = (min + max) / 2;
    if(array_n[i] == array_m[mid]) {
        System.out.println(array_n[i] + "は" + mid + "番目");
        break;
    } else if(array_n[i] < array_m[mid]) {
        max = mid;
        if(max - min == 1) {
            if(array_n[i] == array_m[max]) {
                System.out.println(array_n[i] + "は" + max + "番目");
                break;
            } else if(array_n[i] == array_m[min]) {
                System.out.println(array_n[i] + "は" + min + "番目");
                break;
            }
            System.out.println(array_n[i] + "は見つかりませんでした");
            break;
        }
    } else if(array_n[i] > array_m[mid]) {
        min = mid;
        if(max - min == 1) {
            if(array_n[i] == array_m[max]) {
                System.out.println(array_n[i] + "は" + max + "番目");
                break;
            } else if(array_n[i] == array_m[min]) {
                System.out.println(array_n[i] + "は" + min + "番目");
                break;
            }
            System.out.println(array_n[i] + "は見つかりませんでした");
            break;
        }
    }
}

＊前後のコードは割愛

ざっくり説明すると、目的データと探索元データの中央要素を比較し、一致したならば探索完了なので処理を終える。不一致ならば、目的データが大きい場合、最小要素を軸とし、目的データが小さい場合、最大要素を軸としている。
これによって、軸の値を直接弄らずに、最小要素と最大要素の値を変えるだけで軸を求めることが可能になる。

あとは,最終的な絞込みを行う際の細かい処理を記述しているが、今回主張したいことは2分探索は

最小要素と最大要素の位置から軸を求め範囲を狭めていく

ということだ。これに気付くまでどれだけ時間が掛かったことか…とほほ。

最後に

いかがだったでしょうか？
できるだけ自分の思考プロセスを丁寧に追って記事にしてみました！

正直に告白すると、この課題の途中に2分探索について少し調べてます笑
しかしながら、「これ以上分からない…」というところで何度も頭を捻って必死に答えを探そうとしたのは、良い経験になりました。

そして、その過程をこの記事にアウトプットしているときにより頭の中がスッキリしていることに気付きました。
どこで苦悩し、どこで気付いたのか。
結果ではなく、過程を重視した記事を今後も書いていきたいと思います。

今回は以上です！