スポンサーリンク

二分探索(バイナリサーチ)の挙動テスト

エクセルでは、VLOOKUP関数で近似値検索や、MATCH関数で検索値以下を指定した場合、上から順に検索値を探していくのではなく、全体の真ん中を調べて以上か以下を判断 を繰り返して検索値を探す、二分探索(バイナリサーチ)という動きをしています。

今回はその、二分探索がどういう挙動をしているのか、いろいろテストして仮定を立ててみます。

 

はじめに

今回は実験にMATCH関数の照合の型:1(検査値以下の最大の値を検索、要は以下検索)を使用します。

また、当記事の実験では、正確な答えには辿り着きません。

だってマイクロソフトさんがソース公開してるわけじゃないですからね、あくまでも実験結果から仮定を立てるまでとなります。

 

二分探索とは

まずは二分探索がどういうものか、シンプルな例で動きを確認してみましょう。

例:検索の中から8以下を探す

このように、検索範囲の真ん中チェックを繰り返し、少しずつ検索範囲を狭めて、最終的に答えに辿り着くのが二分探索です。

上から順に検索値を探していくと、この例の場合ならば8を見つけるために8回の検索をする必要がありますが、二分探索ならば3回のチェックで完結しており、処理が軽いというメリットがあります。

そしてこの記事では、10件の真ん中は6じゃなくて5なの?、本当に一致する値を見つけたのに次のデータもチェックしてるの?といった、細かい疑問点を解決するための実験をしていく感じになります。

 

偶数件数の真ん中はどっち?

先ほど、10件の真ん中は5だと書きました。

これが本当かどうかを確認するために、3パターンのテストをします。

 

テスト

1.4番目が一致

 

2.5番目が一致

 

3.6番目が一致

 

まとめ

5番目が条件に一致した場合のみ、結果が#N/Aとならなかった。

10件の真ん中というと、5番目と6番目が候補になるが、この実験から、検索のスタート位置は5番目だという事がわかる。

つまり検索範囲が偶数である場合の検索スタート位置は、真ん中の上側だと予想できる。

式にすると範囲10÷2=スタート位置5となるから。とすれば覚えやすそう。

 

完全一致の挙動

検索値と完全一致した場合の挙動をいろいろ実験してみます。

 

テスト

1.完全一致が連続した場合

 

2.完全一致の次が不一致で、また完全一致に戻る場合

 

3.完全一致の前も完全一致の場合

 

4.完全一致の次以降が条件一致の場合

 

まとめ

二分探索は範囲を半分に、半分にを繰り返していくものだが、検索値と完全一致した場合は次のデータをチェックするのを繰り返しているようです。

また、完全一致の次のデータが条件一致(以下という条件は満たしているが、完全一致ではない)の場合、完全一致が優先される。

MicrosoftサポートのMATCH関数解説では、検査値以下の最大の値を検索します。となっているので、その通りの結果となりました。

 

2回目の検索範囲はどこ?

二分探索は、範囲を半分、半分と狭めていくというものです。

完全一致の場合は、次のデータをチェックするを繰り返してましたが、条件一致の場合は、範囲を半分に絞ってチェックをするように動いています。

というわけで今度は、2回目の検索範囲はどこ?という疑問を解決していきましょう。

 

テスト

今回のテストでは、完全一致の場合は探索を終了させやすいという特徴を利用していきます。

 

1.最初のチェックが条件一致の場合

2回目は何番目のデータをチェックしているのか確認するために、単独完全一致ならそこで探索は止まるという特徴を使ってみました。

その結果、2回目のチェックは、8番目のデータを見ているという事がわかりました。

これにより、2回目の検索範囲を決める時は、前回のチェック対象は除いているという事が予想できます。

つまり、5番目のデータをチェックした次は、5~10の中央(7番目)ではなく、6~10の中央(8番目)をチェックしている事がわかりました。

 

2.最初のチェックが条件不一致の場合

今回初登場、1回目のチェックが条件不一致で、次の検索が上の方になる場合のテストです。

 

これらの結果から、1回目チェックが条件不一致の場合でも、2回目以降の検索範囲を決め方は同じルールが当てはめられるという事がわかりました。

 

まとめ

2回目以降の検索範囲を決める時は、前回のチェック対象は除いて範囲を決め、その中央のデータをチェックし、また次の検索範囲を決める。

これを、答えが出るまで繰り返しているという事がわかりました。

 

空欄の扱いはどうなる?

チェック対象が空欄の場合はどうなるでしょう。

 

テスト

1.不一致と同じ動きか

空欄が以上扱いになる事は無いでしょうから、不一致の以下(0扱い)になるのかを確認。

この結果から、空欄と0は別物扱いという事がわかる。

そして、結果が3番目となっている事から、最初のチェックでは検索値を超えていると判断された事がわかる。

そこで、空欄の場合は検索対象を一つ下げているのではないか。という仮説を立てて実験していきます。

今回の場合5番目が空欄なので、6番目の9が最初のチェック対象となったのでは?という事。

 

2.空欄の場合チェック対象が1つ下になる場合の動き

これなら結果が3になった理由に納得できます。

 

3.空欄が続く場合

この結果から、空欄が続く場合、何か値を見つけるまで下に進み続け、値を見つけたところでチェック。

そして次の検索範囲には空欄も含めており、その範囲の中央を次の検索位置としている事がわかる。

それを証明するのが下のパターン。

 

.最初のチェック対象が一致(検索値未満)の場合

検索範囲を下側に狭めていく場合、想定通りに動いているか実験してみましょう。

 

.最初のチェック位置含め、それより下が全て空欄の場合

要は下半分が全部空欄だったらどうなんの?って事。

先が全部空欄だったら、最初のチェック対象を未満として扱って上側に検索再開するようですね。

 

.2回目以降のチェック対象が空欄の場合

初回チェックが空欄の場合にどう動いているかは、まだ言語化できるのですが、2回目以降についてはなんかこう、感じ取ってください。

だいたい想定している動きではあったのですが、こんなん文章にできるか!って結果になりました。

人によっては、あーそっちが優先されるのかーって思うかもしれません。

 

 

 

まとめ

色々試してみた結果、チェック対象が空欄の場合、1つずつ下に移動している事がわかりました。

あと、チェック対象以降が全部空欄の場合は未満とみなし、検索範囲を上方向に絞って仕切り直してますね。

ただし、2回目以降のチェックで空欄を引き当てた場合は、前のチェック結果が影響する事で混乱しそうになる。(完全一致としての挙動が優先されるなど)

 

二分探索の動きを整理すると

ここまでの実験で、エクセルでの二分探索は、基本は以下のような動きをしていると予想できます。

  • 検索範囲の真ん中にあるデータをチェック(検索範囲が偶数なら1つ上が選ばれる)
  • 完全一致の場合は次のデータとの比較を繰り返す
  • 検索値未満なら下方向、超なら上方向を探索していく
  • 次の検索範囲を決める時は、前回チェック対象となったデータは除く
  • 空欄の場合はチェック対象を次のデータにする
  • これを繰り返し検索範囲を狭め、最後の1つになったところが答えとなる

 

ただ2回目のチェック以降で空欄を引き当てた時の動きが言葉では表現しにくいので、感覚で悟ってください。

 

おまけテスト

出番の無かったテスト結果をここに供養しておきます。

 

 

 

コメント

タイトルとURLをコピーしました