二分探索の平均探索回数

質問

こんにちは、
二分探索の最大探索回数がlog2N+1なのは
書籍にある計算式の変換で理解できたのですが、平均探索回数がlog2Nなのが理解できません。
書籍では『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』と書かれていますが
どういう意味なのか判りません。

そこで具体的に考えてみました。
例えば8個のデータの中から探す場合、
a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]
とデータが並んでいて、
それぞれの位置に目的の値が入っていた時の探索回数は、
3回、2回、3回、1回、3回、2回、3回、4回
と考えました。
a[1]の場所に目的の数があった場合、
2回目の探索で見つかる、という意味合いです。
最大探索回数はa[7]の時に4回となり、log2N+1になっています。
この考え方でNを増やしていった所、最大探索回数はlog2N+1になりそうです。

そこで上記の場合の平均探索回数の方は、
(3+2+3+1+3+2+3+4)/8
と計算し、2.625と考えました。
この考え方でNを増やしていくと
16コ：3.375
32コ：4.21875
64コ：5.125
128コ：6.0703125
…と、
平均探索回数がlog2Nではなくlog2N-1に近づいていきます。

考え方の間違っている箇所の指摘をお願いします。

回答No.5

jjon-com

私は情報処理技術者試験の参考書で，二分探索の平均探索回数は（log2N ではなく）[log2N] だと勉強しました。[ ] はガウス記号と呼ばれ，その数を越えない最大の整数を表します。また，最大探索回数はこれに１を足した値 [log2N]+1 で，どちらも整数値で求めることになります。

Nが15の時は，[log2(15)] = [3.906…] なので，
平均探索３回（Miyabiさん計算 3.266），最大探索４回

Nが16の時は，[log2(16)] = [4] なので，
平均探索４回（Miyabiさん計算 3.375），最大探索５回

……となって，最大探索回数は正しく求められています。その反面，要素数が１つ増えただけで平均探索回数が一気に１回分増える境界があるわけですから，整数で求めた平均探索回数の値にはアバウトさが見られると思います。

回答No.4

sakusaker7

いろいろ調べたところ、以下のようなページが見つかりました。

Average Case of Binary Search
http://www.mcs.sdsmt.edu/ecorwin/cs251/binavg/binavg.htm

Dividing by n to get the average gives
A=k + k/n -1

Notice that for large n, this is about k–1. Thus, the average case is only about one step better than the worst case.

どうも途中でよくわからなくなってしまったのですが、
具体的な値を当てはめて考えるとかえってわかりづらくなってしまう
のかもしれません。

補足

いくつかページを紹介して下さり、ありがとうございます。
私なら検索で引っかかっても英文を見た時点で中身に目を通さなかったと思います。

翻訳した時点で、意味が判らず、
数式を見て、一旦は判った気になったけど、また判らず…。

とにかく、
高校数学で極限を求める時のように、
具体的な数値で考えずに証明した方が上手くいくかもしれない事は判りました。

捕まえれたら数学の先生に聞いてみたいと思います。

回答No.3

sakusaker7

はじめにお断りしておきますが、わたしは数学に関しては不得意なほうですので、
見当はずれのことを言っている可能性があります。
正確を期すならその方面の識者にあたるなりしてください。

んで、質問者さんが実際の数値として平均回数を求めようとして
色々計算していらっしゃいますが、なんとなくですが、単純に
算術平均(相加平均)を使っては目指す数字が出ないのではないかという
気がします。

質問に対する回答（２）
http://www004.upp.so-net.ne.jp/s_honma/question/question2.htm

面倒くさいので相乗平均使ったらどうかとかは確かめていません。

あと、ぶっちゃけ
全部を探索しつくすのに必要な回数が log2(N) + 1
なのですから、(少なくとも)半分を探索しつくすのに必要な回数
= 平均探索回数は最大探索回数のひとつ前、つまり log2(N)
になるという考え方では納得できませんか?
それに小数点以下の部分は切り上げて考えるべきことがほとんどでしょうから、
log2(N)-1 <= x <= log2(N)
の範囲になっているのならあまり気にすることもないんじゃないかと。

たとえば平均値として6.5回という数字が出たとして、0.5という数字そのものには
切り上げて全体を7にするという役目以外に意味を見出せません。

補足

相乗平均はこの場面で使うのが妥当かどうなのかも判りませんが、
平均を取る値が2つ3つではないので、具体的に試すこともできないです…。

> 全部を探索しつくすのに必要な回数が log2(N) + 1
> なのですから、(少なくとも)半分を探索しつくすのに必要な回数
> = 平均探索回数は最大探索回数のひとつ前、つまり log2(N)

本に書いてある『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』
という意味が判りました。
具体的な数値を調べる以前なら、
「最大探索回数が7回の時、7回で見つかるのが全検索結果の約半分を占めてて、1～5回で見つかる時は少ないから
平均すれば6回前後になるのかなぁ」とおぼろげに納得したのでしょうが、
具体的な数値を出したり、Nを増やすとほぼlog2N-1になるのを見てる現状では、う～ん…、といった所でしょうか。
明らかに"-1"が出てくると

- - - -

ちなみに今までの質問・補足で参考にしてる書籍は基本情報技術者の対策本、
「3週間完全マスター 基本情報技術者 2004～2005年度版」で
別の「2001年度版 基本情報技術者 標準教科書」を見た所、"比較回数"については

A:線形探索の平均比較回数 n/2
B:線形探索の最大比較回数 n
C:二分探索の平均比較回数 [log2n]
D:二分探索の最大比較回数 [log2n]+1

* [ ] はガウス記号で[ ]内の値を超えない最大の整数を表す

と書かれています。
また、要素数が10,100,1000,10000の時のそれぞれの回数も書かれていますので10000だけを挙げてみると

A:5000
B:10000
C:13
D:14

とあります。
その次の節では計算量の話が述べてあり、各探索の"計算量"では

a:線形探索の計算量 n
b:二分探索の計算量 log2n

nの個数が10000の場合は

a:13.3
b:10000

とあります。

確かに、二分探索の最大比較回数は最大で何回調べるのか、なので
7.5などと小数点が付いてはいけないから小数点以下の処理をしなければなりません。
で、この場合は小数点以下を切り捨てるのが正しいので上の[ ]の記述は正しいと思います。
では、平均比較回数の方は小数点以下を切り捨てなければいけないのでしょうか。
また、計算量の所では13.3と小数点以下を切り捨てていません。

たいていの本では線形探索の平均探索回数はN/2とありますが
別の本で、(1+n)/2となっていたのを見て、「厳密に書いてあるなぁ」と思ったのですが、
その本の二分探索の平均探索回数はlog2Nになってますね…。

回答No.2

sakusaker7

そりゃためしに挙げているデータがよくないです。
例えば8個のデータの中から探す場合、
> a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]
> とデータが並んでいて、
> それぞれの位置に目的の値が入っていた時の探索回数は、
> 3回、2回、3回、1回、3回、2回、3回、4回
この場合だと、8個から15個までは最大検索回数が4回に収まりますよね。
そのなかで8個というのは最小のものですから、

> (3+2+3+1+3+2+3+4)/8
> と計算し、2.625と考えました。

としてしまうと、ひとつ下のレベルの数値、log2(N)-1に近づいていってしまうというわけです。
ためしにデータ数を15、31、63といった数字で計算してみてください。

> 書籍では『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』と書かれていますが
> どういう意味なのか判りません。

たとえば線形探索だと、
運がよければ最初の要素で当たりを引けますが、最悪だと最後の要素になります。
大体何回検索すると当たりを引けるかというのがN/2になるという理屈はいいですか(単なる算術平均です)?

二分検索の場合は、
1回で当たり→1個
2回で当たり→+ 2個
3回で当たり→+ 4個
4回で当たり→+ 8個
...
のように個数が増えますが考え方は同じで、半分調べつくすのに必要な回数を考えれば、
全体での平均の回数がわかるというわけです。

補足

> ひとつ下のレベルの数値、log2(N)-1に近づいていってしまうというわけです。

私も当初、Nを一つずつ増やして調べた値はlog2Nのグラフに対して振動しているだろうと思って細かく調べていきました。

Nが7の時は、
(3+2+3+1+3+2+3)/7 = 2.428…、と計算しました。

> ためしにデータ数を15、31、63といった数字で計算してみてください。

上のNが7個の様に調べると、(左が実際に調べてみた値/右がlogを計算した値)
15コ：3.266… / log2(15) = 3.906…
31コ：4.161… / log2(31) = 4.954…
63コ：5.095… / log2(63) = 5.977…
127コ：6.055… / log2(127) = 6.988…
255コ：7.031… / log2(255) = 7.994…
511コ：8.017… / log2(511) = 8.997…
1023コ：9.009… / log2(1023) = 9.998…
2047コ：10.005… / log2(2047) = 10.999…

と、最大探索回数が同じ中で最大のNを挙げても傾向が変わりません。
Nを2のn乗ずつではなく、一つずつ増やしていってもlog2N-1に近づいていくように見えます。

> 大体何回検索すると当たりを引けるかというのがN/2になるという理屈はいいですか(単なる算術平均です)?

線形探索の場合、最大探索回数がN、平均探索回数がN/2になるのは理解できます。

> 二分検索の場合は、

に書かれているような値を計算しています。
Nが15の時、
1回で当たりが1個
2回で当たりが2個
3回で当たりが4個
4回で当たりが8個
を( 1*1 + 2*2 + 3*4 + 4*8 )/15 = 3.266 と求めているのですが…。

- - - -

平均探索回数という意味がそれぞれの探索回数を合計し要素数で割るという受け取り方が間違っているのか、
もしくは具体的な探索方法が違ってる気がしてるのですが、どうでしょう…。

回答No.1

osamuy

Nが十分大きければN+1→Nとみなせるので、log2(N)と言ってるのでは。
計算量を考えるときは、たいてい定数項は無視しますので。

＞『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』
こっちは、ソートされてないデータについての検索の話では。

補足

引用が大きくなりますが…
『二分探索では～…

略（最大探索回数をmとすると N*(1/2)^(m-1)=1 → m=log2N+1 になる、という説明）

～…つまり、最大N個のデータを探索するのに、最大でlog2N+1回、
平均でlog2N回探索すればよいことになります(平均探索回数の場合、N/2個のデータ探索をすればよいと考えます)。
従って、二分探索の計算量はO(log2N)となります。』

とあります。

> Nが十分大きければN+1→Nとみなせるので、log2(N)と言ってるのでは。
書籍にも「O記法(オーダー記法)ではnの係数やnに加減される定数は無視」と書かれているので
最後の行の計算量がlog2Nというのは理解できます。
その一つ前の行の『平均でlog2N回』というのが腑に落ちなかったのですが、これもO記法の意味合いで書かれているのでしょうか…。
ただその後ろの括弧書きの意味が判らないのには変わりありません。

> こっちは、ソートされてないデータについての検索の話では。
文章の頭に二分探索ではとあるので、多分ソートされている前提で語られていると思うのですが。