二分探索とは何か
はいこんにちはえ今回は2分単作という
ものを解説していきたいと思いますえ注意
して欲しいのは2分単作2つに分けて探索
する方法のことであって2分探索ではない
ですそんななんかあの友達が家の中で
スマホなくした時みたいな探し方の話じゃ
ないですえ皆さんねもっとね探してあげて
ください2分以上はいということで今回
やっていく2分単作とは何かと言とソド
済みの配列に対する効率的な探索
アルゴリズムのことですえこれが具体的に
どういう意味かってのは例を通して話して
いきたいと思うんですがままずこの二分
単作が日常生活にどう役立つのかの話をし
ましょうこれはね結構ねえ考え方によって
はたくさんあるんですけどもま例えばえ私
いくつに見えるって言われた時にね
なるべく早く言い当てる方法につがったり
とかえあとは辞書の中で特定の単語を探す
時にまあなるべくね早く見つける方法に
繋がったりとかしますまあのヒントになっ
てすですねそういう時のなので是非ですね
ま普段プログラミングとかねえしない人も
え聞いてくれたら嬉しいですではですねえ
早速例をやってみましょうえまずここに
データをね並べてみましたはい数のデータ
が並んでいますで今適当に並べるんじゃ
なくて小さい中にね並べていますえ今回
データにえ重複はないとします全部え違う
数字が今小さい順に並んでいるま今言った
みたいに小さい順に並べるとかのことをね
え相当って言いますえ相当ってのはま一定
の規則に従って何がねデータの集合を
並べることなんですが今回はえ小さい順に
数を並べみましたはいで今この数字はなん
かね外から見えない箱の中に隠れてると
思ってくださいはいその中で今回は27を
ね探していきたいと思います本当はここに
ある27を探していきたいはいまずその
ためにですねこのデータに番号を振って
あげ
ましょうはい今番号振ってきました1番で
12番で33番7っていう風に今ここに
あるデータに番号を振ってあげただけです
はいというわけで今からね27を探して
いきたいんですがま1番単純に考えたら
こういう探索の方法を浮かびますよねえ
もう小さい順からここかなってあ1だっ
たら違うわじゃ次ここかな3だったら違う
わじゃ次ここかな7だったら違うわって風
にもうしらみつぶしに小さい順から開けて
いく方法これをですね線形探索って言い
ますはいま直的にも分かるようにあまり
効率のいい方法とは言えなそうですよね
まあだってあの名探偵とかね名形事がえ皆
さんお集まりいただきありがとうござい
ますとりあえず背の順に並んでくださいえ
じゃあ小さい方からあなたが犯人ですね
違いますかごめんなさいじゃあ次あなたが
犯人ですね違いますかごめんなさいあなた
が犯人ですねってやってるような感じなん
でまあまりね賢い方法でないですえ特に
このデータのね個数が増えてくると線形
探索ってねえすごく大変になりますえなの
で今回やってくのはそういう風になんか
しみつぶしに探していく方法じゃなくてだ
からせっかく相とされているんだったら
もっとうまい方法があるんじゃないかと
いうことなんですねえそこで出てくる考え
方がこの2分単作という2つに分ける探索
アルゴリズムですえではその方法をこっち
で解説していき
ましょうでは2分探索をやっていき
ましょうえまず始めることはデータの中で
真ん中になる場所を計算して探すことです
えなので中央の番号を計算します
はいえ今データは1番から10番まである
のでその真ん中ってのは最小値と最大値を
足して2で割ったところですよねなの
ではいこれです1/2+10これ計算する
ともちろん
5.5え5.5番というね番号はないので
え今回はこれを切り捨てしたいと思います
えちなみに別に切り捨てでも切り上げでも
どっちでもいいんですが今回は切り捨てに
しましょう
はいというわけで5という数字が出てきた
のでえこれはですね5番目のデータを調べ
なさいという意味ですえでは5番目の
データを実際調べてみますそうしたら12
でした12ということは今我々が探して
いる27ではないですよねえ違いましたと
えただそれだけじゃなくてもっと分かる
ことがあるんですね今このデータっていう
のは小さい順に並んでいるんだからこの箱
を開けたら12だったんだったらこっち
よりも左はもう全部可能性がないですよね
だって今重複がなくて小さい順なんだから
こっちにはもう12により小さいものしか
並んでいないはずだからなので左側のもう
可能性なくなり
ますはいなので今我々が探すべき候補なの
はもう6番から10番のとこに絞られてい
ますなので今2つに分けてもうねえ片方は
可能性がなくなってしまったんですねこれ
が2分単作のえ考え方です2つに分けて
もうねえなくしててしまうえなので次から
もやることは同じでは丸2番今残ってる中
の中央の番号を決め
ましょうはいえ今残ってるものの中で最小
値は6で最大値が10なので計算
ははい62+10えもちろんこれは
8なので今残ってるデータの真ん中の8番
目を調べましょうってことですね8番目を
調べると実際には25という数字が出てき
ますあこれも違いましたとでさっきと同じ
ようにもうこれよりも左側ないのでこれも
もう可能性なくなりますはいというわけで
えもうねま2択になってるんですけども
もっとねデータが多い場合のこともねえ
含めて考えられるようにえこのね探索
アルゴリズムを続けていきたいと思います
一応しっかりとえもう1回やっておき
ましょう丸3番今残ってる中での中央の
番号を決め
ますはいえこれは残ってのはQと10だけ
なの
で92+10でこれ計算するとま192で
はんので
9.5え切り捨てをし
たら9ですねえなので9番目のデータを
調べますはいそしたら27でしたとで今
もう重複もないのでえこっち側の可能性も
なくなってあ9番目のところに我々が今
探してる27があったのでということで
ですねえこれで終了
ですはいというわけでこういう風に2つに
分けていってどっちかの可能性をどんどん
なくしていくという方法がですねえ2分則
の考え方になりますえちなみにこれは
ものすごくねえ細かい話なんですけども
興味がある人はね聞いてくださいえ今この
中央の番号を出すためにえ2のね最小値+
最大値まつまりこういう計算をしたんです
ねはい2のまミニマム+マッスとえただ
ですね実際にえプログラミングで実装する
時にはこう計算した方がいい
ですはいミニマム+
2-ミニマムといや別にこれはなんかねえ
計算したらこれと同じになるんじゃないか
とね思うと思います別に数学的には正しい
ですえこれをねえしっかり2/2で通分し
てあげれば別に同じ22ミニマム+マに
なるんだけどもプログラミングで実装する
時には実際にはこっちの方がいいとえこれ
がなぜかという話なんですけどま
プログラミングのねえ怖いとこで面白い
とこでもあるんですがこのえこれを計算
する過程でミニマム+マックスって値計算
するんですねまそうすると残ってるものに
よってはですね結構数が大きくなって
しまうとそうするともう準備されてる整数
の上限を超えてしまう可能性があるとこれ
を計算した段階でそうするとえまおかしく
なってしまうのでまこういうね巨大な数字
がなるべくね現れないようにするのがえ
実装上の注意なのでこれが現れないように
ただ数学的には同じ意味のまこっち側でね
計算するというのがまよく行われるので
実際にね組んでみたい人はま気にしてみて
くれたらいいなと思いますますごいね
データの数が多くなってきたりするとそう
いうことが発生しうるのでまこれはね引算
しか出てこないのでえ急激にね大きくなっ
たりはしませんというま少しねえ外れた
余談でし
たはいというわけでま多くの人にとってね
興味があるのはこれは本当に実際早いのか
という話ですねえなのでこれの早さんに
ついてもう少しえ詳しく調べてみ
ましょう無力になったみたい
にでは実際に探索に必要な回数を評価する
時間計算量というものの話をしていきたい
と思いますえまず一般にn個のデータが
あるとしましょうえさっきはね10個しか
なかったんですが今回もっとね多くの個性
のデータがあると想像しておいてください
でその時にこの時間計算量って何を考える
かというとえ通常はですねえ探索に必要な
回数が最大つまり最悪なケースで何回え箱
を開けなきゃいけないかで考えますえ線形
探索でまず話をするとN5のデータがある
場合に最悪なケースってどういう時かって
言うともちろん白みつに端っこからやっ
てったのに本当の正解が反対側の端っこ
だった場合ですよねその時って何回箱開け
てるかって言うとそれはもちろんn回箱を
開けてますねなので最悪な場合ってのはま
n回になるわけですたこの時間計算量って
普通はもっとですねえざっくりとした物見
方をしますどういうことかと言うと例えば
え最大の回数がこうなったとする
とはい例えばですよ4nの3+2nの2+
3N+5になったとするとで通常
めちゃくちゃねNが大きいのでここでもN
が大きいケース考えますそうするともう
ここら辺って4Lの3乗に比べたらもう
ゴミみたいなもんですねだって大きい数の
3乗するからだからからほとんどですね
主要な子はここだけになりますNが大きい
場合ってそしてもっとねざっくりとした物
の見方をしてこの4倍とかももはやNが
大きい場合はそんなに影響ないよねという
ことでもしこういう風な回数だったらです
ねこれをもう大体nの3乗ぐらいではと
考えますその時にこのLの3乗ぐらいって
いう考え方をしましたというのをね表す
ためにえビッOという記号を使いますはい
このOの大文字でnの3と意味はだからn
の3乗ぐらいのオーダーですよと言ってい
ますこういうのをオーダー基本って言い
ますなので今からこの線形探索も2分探索
もえ時間計算量の考えでよく使われてる
ようにえオーダー記法を使っていきたいと
思い
ますはいませっかくねこんな話をしたん
ですがえ今回この線形探索の場合は効果不
効果ですね本当に最大回数がNなのでま
オーダーも普通にNになり
ますはいまこれぐらいの回数がかかる
でしょうってことですねまやっぱりま
かかりますねだ100万個とかデータが
あったらま大体ねその100万回のえ最大
の探索回数がかかってしまうとというわけ
で次は2分探索がどうなるかという話なん
ですがこれはですねえしっかりと聞いて
もらえればすぐに分かると思います元々え
あるデータの個数ってのはn個で1回箱を
開けた段階でもう半分のね可能性がなかる
えなくなるんでえ残ってるデータの個数は
ま2のNになりますええただですね正直え
データの個数が偶数の場合と奇数の場合で
少しね扱いが変わってくるんで細かい話は
ですねえどうせオーダーで考えるんで忘れ
てくださいまざっくり1/2n個になり
ますよねでもう1回箱を開けたらまた候補
が半分になる2の2/になるとでもう1回
箱開けたら2の3になるという風に
どんどん調べていったらえ候補のデータの
個数が半分になってくんですねで1つに
絞れる瞬間というのが警戒目だとし
ましょう
つまり2の計のNになった時に1になって
まこうやって1つに絞れたという時がま
最大の回数ですよねこのえなのでこれをK
について解いてあげるとえ2の形状を払っ
てlog2を取ってあげれば出てK
=はいlog2のNということでこれが
ですねまざっくりとした最大の回数なわけ
ですま今はねさっきも言ってるように本当
は偶数奇数でね残ってるデータの数に対し
て本当はま+1とかされたりするんですが
まもうざっくり言ったらねl2のNでいい
ですよねえなのでオーダー
もはい群2のNになりますえちなみに少し
余談なんですがもうねえこういう分野では
底を書かないことも多いですえなんで
かって言うと底の変換公式でえ全部手変え
られちゃうんですねま底変えたらもちろん
その係数がついちゃうんですがこの
オーダー基法って係数無視するんで別に底
を変えても係数分しかずれがないんでま
普通にねえ2を書かなかったりすることも
多いですただ今回ねえやったことがえ
思い出しやすいように一応ね書いておき
たいと思いますま別これでも間違いでは
ないですはいというわけで2分単作の場合
はまあねえ時間計算量このオーダーが
log2のNなことが分かったとまつまり
これだいぶ効率いいですよねNが大きい時
はえ特にだてNがめちゃくちゃでかいとね
logっていうね対数でめちゃくちゃね
数字を抑えてくれてるんでめちゃくちゃ
効率が良くなってるということなんでま
特にですねデータがすごく大きい場合にま
何かね相当されたものに相当された配列に
対して探索をしたい時にはえ2分探索をね
使うといいよという話なわけですこれで
今回の解説部分は以上なんですがまなんで
ね最初に話した日常生活でどう使うかって
言となんかまあねえ私何歳に見えるって
言われてまあ本当にざっくりとまあ20
から40だなと思った時にましっかりねえ
20ですか21ですかとかじゃなくてまあ
2分探索しようと思ってえ30歳ですかあ
ごめんなさいそれよりえ上でしたかみたい
な感じでえやってくのがいいって話をし
てるんですねあの他にも何か私の誕生日
わかるって言われた時にうん適当になんか
1月1日から違う違う違うってやるんじゃ
なくてまざっくりねえ真ん中のその7月1
日って言って違うそれよりもえ早いよとか
言われたらあ早いんだとかっていう風に
探索していくといいと思いますはい
もちろんですねこれ本当に真似しないで
くださいねえ20から40ぐらいの女性に
対してえ線形探索をした方が絶対に幸せに
なります20ですかせそんなに若くない
よってね言われた方がいいですとことで
今回の授業は終わりお疲れ様でし
た届こんな声よ何年でも声てなっ
てとかって
描き直し
立ち尽くす方が痛いから
さ