Sachool Engineering Blog

プログラミング学習の記録

課題報告　探索アルゴリズム【失敗編】

| Comments

どうも！仙台ファクトリーのkouです。
探索アルゴリズムと格闘した報告をしたいと思います。
無知であることをお許しください。。。

問題文

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

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

端的に言うと、 1万個の数値の中から目的となる100個の数値を素早く見つけるアルゴリズムを考えるというものだ。

問題文を見てふと思ったこと

  • 与えられた1万個の乱数の配列が既に「昇順」に並んでいる→2分探索が使える
  • 目的の数値も並び替えれば探索が早くなる？（漠然と）

2分探索については、前回の課題であるアルゴリズムとフローチャートについての調査でざっとやっただけでロジックの理解は曖昧な状態である。このロジックを考えることが今回の課題を解決する鍵になりそうだ。

早速問題に取り掛かるが…

＊これ以降は、問題文の1万個の数値を『探索元データ』、100件の目的数値を『目的データ』と表記する。

最初に考えたロジックが次の通りだ。(２分探索まがいのことをやっているつもり…)

用意

探索元データの配列 array_m[10000]
目的データの配列 array_n[100]
探索元データの中央要素の添え字をmid
探索元データの軸をjiku
とする。

＊お気づきかもしれないが、jikuという意味不明な変数を用意してしまったのが、どハマリした原因である。

方針

  • 探索元データの中央要素と目的データを比較

データが一致したなら探索終了。不一致なら探索継続。 ここでは、if(array_m[mid] == array[0])、if(array_m[mid] > array[0])、if(array_m[mid] < array_[0])といった単純な比較を行っている。 2分探索に理解のある人はここまでなら理解できるはず。2分探索は基本的にはこの繰り返しである。 つまり、midの値を分岐に合わせて調整して比較していくということである。midが軸なのである。

しかし、私はここで魔法の変数jikuを用意してしまった。 これ以上、文章で解説するとややこしくなるのでコードで構造を示す。

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
34
35
36
37
38
39
40

//例）目的データの最初の要素を探索するプログラム

// mid = 5000（要素数/2）
// jiku = 0

if(array_n[0] == array_m[mid]) {
    //探索終了
} else if(array_n[0] > array_m[mid]) {
      mid = mid / 2;
      jiku = 3 * mid;

      while(flag) {
      if(array_n[0] > array_m[jiku]) {

      }
      else if(array_n[0] < array_m[jiku]) {

      }
      else {
        //探索終了
      }
  }

}　else {
    mid = mid / 2;
    jiku = mid;

    while(flag) {
    if(array_n[0] > array_m[jiku]) {

    }
    else if(array_n[0] < array_m[jiku]) {

    }
    else {
      //探索終了
    }

    }
}

最初はmidを使い比較して2回目以降、midの値をjikuに移し比較している。 if文の中の処理は省略しているが、ざっくり解説すると

  • midの値を半分にする
  • midの値をjikuに足し引きしている

ということを行っている。 目的データとjikuを添え字とする探索元データの配列要素と比較を行い、目的データの値が大きい場合は、midの値をjikuに加算し、小さい場合は、midの値をjikuに減算している。

問題点

  • 探索元データが存在するのに探索を終了する場合がある

探索元データの要素数を1万とした場合、midの値は5000,2500,1250,625,,,,,,,19,9,4,2,1と 半分になっていく。しかしこの場合、終盤の細かい部分の探索が粗くなってしまう

以下に出力結果の一例を示す。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

探索98回目
5822の探索を始めます
midの値は2500jikuの値は7500
midの値は1250jikuの値は6250
midの値は625jikuの値は5625
midの値は312jikuの値は5937
midの値は156jikuの値は5781
midの値は78jikuの値は5859
midの値は39jikuの値は5820
midの値は19jikuの値は5839
midの値は9jikuの値は5830
midの値は4jikuの値は5826
midの値は2jikuの値は5824
midの値は1jikuの値は5823
midの値は0jikuの値は5823
発見できませんでした

このように範囲を絞りきる前に、midの値が0になってしまうことがあった。
そしてここで暫く行き詰ってしまった。。。

結局、解決策が浮かばなかった件

あと一歩のところで解決できそうな気がするのだが、これ以降前に進まなかった。
そしてあれこれ考えている内にあることに気づいてしまったのである。

続きは
課題報告 探索アルゴリズム【成功編】で！

Comments