二分探索とは何か
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2024
- 「私何歳に見えますか？」
そう言われたときの効率的な対処法
(やすの余談)
私が会社に勤務していたころ、新人なのにあまりに落ち着いているため、あだ名が「次長」になりかけました。
------------------------------------------------------
予備校のノリで学ぶ「大学の数学・物理」のチャンネルでは主に
①大学講座：大学レベルの理系科目
②高校講座：受験レベルの理系科目
の授業動画をアップしており、他にも理系の高校生・大学生に向けた様々な情報提供を行っています
＜クラウドファンディング＞
このチャンネルは皆さまからのご支援で成り立っています。
応援してくださる方はご協力お願いいたします
camp-fire.jp/p...
＜公式HP＞
▼公式HPトップページ
yobinori.jp
▼動画一覧
yobinori.jp/vi...
▼おすすめの教科書や参考書
yobinori.jp/re...
▼お仕事・コラボのご依頼
yobinori.jp/co...
＜メンバーSNS＞
▼X
たくみ(講師)： / yobinori
やす(編集)： / yasu_yobinori
▼Instagram
たくみ(講師)： / yobinori
やす(編集)： / yobinoriyasu
▼note
たくみ(講師)：note.mu/yobinori
やす(編集)：note.mu/yasu_y...
▼公式グッズ
以下サイトで販売中
suzuri.jp/Yobi...
------------------------------------------------------
【エンディングテーマ】
“物語のある音楽”をコンセプトに活動するボーカル不在の音楽ユニット”noto”（ノート）
TH-camチャンネル『予備校のノリで学ぶ「大学の数学・物理」』の主題歌として書き下ろした一曲。
noto / 2nd single『Telescope』（feat.みきなつみ）
*****************************************************
noto公式TH-camチャンネルにてMusic Video フルver.が公開中！
【noto -『Telescope』】
• noto -『Telescope』（feat...
【みきなつみ公式TH-cam】
/ @mikinatsu_official
存命人類の最高年齢が116歳だから
「いくつに見える？」と聞かれたら58から二分探索開始する
「怒ってる理由わかる？」って言われて思い当たるのを時系列で二分探索してったら余分に怒られた。
実際にやってみるところが尊敬します
理由わかってないって伝えてるのと同値で草
マジレスすると、
余分に怒られる量が、線型探索だった場合より少なく済んでよかったな、と、学ぶ動画だと思う
余分探索？
めっちゃ面白いw
配列の添え字が0から始まらないとムズムズしている人はいるはずだな？
結構違和感があるよね
はいはいここにいますw
稀に1始まりの言語もあるようでw
「(いま日本の最高齢が116歳らしいから…)うーん、58歳！」みたいな話じゃなくてよかった
それよりも若いよ、とか言ってくれずに全てが終わりそう（ある意味もっとも早い探索終了）
ちょうどプログラミングの授業で取り扱いました😅
物凄く分かりやすかったです
とても解り易く素晴らしかったです。本当にどうも有難うございました。
電子レンジで何分温めたらいいかわからない？wフッフッフw心配することなかれwwこんな時にも役に立つのが競技プログラミング、伝家の宝刀†二分探索†を使わせていただきますぞ！wwwまずは時間を(0+2e9)/2=1e9分にセットして……\ﾎﾞﾝｯ/グオーーーー！！！！！！！！家が燃えてしまった……(悲しい)
高校生の頃にAtCoderにハマっていればなあ...
情報系で使う内容の動画もっと見たいです！！！！
学校の課題研究で選んだ研究テーマだったのでありがたいです！
こんなにわかりやすいのがプログラミングに使われとるんか〜と思いながら聴いてました
ウミガメのスープ好きなので割と意識してやってます。
7/1生まれのワイ、バグる
うぽつです＿|＼○＿!!
女の子に年齢聞く時は線形探索。これ間違いなし。
0:41
答えに近づくにつれてめちゃくちゃ機嫌悪くなりそう
これはこれから競プロの解説シリーズが始まる予感？
急にビッグオーという単語が出てきて勝手に驚く自分(笑)
とあるメガデウスが頭を過ります
ありがとう。
数値計算でも二分法というものがありますね。
ニュートン法はさらに収束が早い。
理系は二分探索、文系は二項対立か。言い得て妙ですね〜笑笑
バイナリサーチにかかる時間ってみんなlogで評価するんだけど、ソート必須なんでそれだけじゃないだろっていつも思う。
なんか「送料別」みたいな。😅
ソートは二分探索の付き物じゃないからね、、
M回探索するならソートして二分探索がO((M+N)logN)、ソートせず毎回線形探索するとO(MN)。
Mが1桁とかごく小さいうちはソートせず線形探索でゴリ押したほうがよくはなりますね。
@@habu1010 ですです
詰将棋を解く時間を最短にする場合の王手のかけれる数の降順表記での降順ソートからの平均解答時間と、
残っている持ち駒に評価係数を足した変則的評価値での降順での平均解答時間で10問試してみたことがあったような記憶・・・
最近将棋ソフトは速度が速くなりすぎて力業本線でこういう話はないがもしよければこういうネタいかが？
高校で情報系科目が強化され、大学入試にも関わってきています。情報学に関する動画は、楽しみです。制御理論の研究をしていても、アルゴリズム分野（情報学分野）の手法を取り込むことで良い成果がでるケースもたくさんあるので、研究者目線でも情報系科目に関する様々な動画が出るのを期待しています。
なお、何歳に見えるかを聞かれて２０～４０と思ったのだったら、迷わず２０と答えます。
@user-vg6jx5do7i 強引に20にしか見えんで押し通す方向で。それができないなら初めから二分探索するしかない。
長くプログラマをしています。
まさか上限値を超えない演算のことまで解説されるとは思わず、「そんなことまで知ってるんか…」と大変感嘆しました。
素晴らしい動画をありがとうございました！
わお
年齢は線形探索したほうが、会話してる時間も長くなるから一緒にいられる時間も増えていいことづくめですね
探索もソートも面白い
数学なんて全然できなかったけどプログラミングやってから数学すげええって思うようになった
エンジニアの身からすると、こいういアルゴリズムまで解説してくれるのは分野に新規が流入してくれる機会につながるからかなりうれしい
それと同時に、今の若者が怖くなる
オチが理系あるあるで草
ワイ「最も若いのは0歳、最高齢はギネスで122歳だから二分探索でまず61歳から始めよう、61歳いｊ(((」
俺の場合、7／1より前ですか？って聞かれると、多少の間の後いいえって答えるから即7／1生まれとバレるかも
即答できるだろ
川原できれいな石探すのが趣味なんで、こんど川原に行ったら全体を二分探索してみようと思いましたが
よく考えたら石ころのソートなんてされてないカオスな場所だった（誰かソートしといて）
オーバーフロー対策まで解説されてる!流石ですね。
大きい数字を扱わないと忘れがち。
ふたまたニョキニョキだ!
頭が固くて学生の頃リアルに二分探索で辞書引いてたけど相当遅かったわ
他の人がやってるのは26分探索？だもんね・・・
めちゃくちゃわかりやすいです。
ほかのソートに関しての動画も楽しみにしてます！
アルゴリズムとかあんま知らんけど、クイックソートの探索版って感じかな？
年齢を当てる時は線形探索の方が幸せ は笑った
ちょっと閣下の年齢を当てに行きたいな
アルゴリズムシリーズ始まるとしたらめちゃくちゃ嬉しい
2021年M-1でモグライダーがこれに関するネタをやってましたね
14:20「誕生日は7月1日?」
オレのように7月1日だと「はい、そうです」ですぐ終わってしまう😅
(max+min)/2を計算しようとするとオーバーフローする可能性があるのは、クヌース先生が指摘していたような。そんな細かいことを無視する教本が多いので、何冊読み込んでいるのだろうか。。。
アキネーターじゃん？生きていますか？
はい/いいえ
人間ですか？
はい／いいえ
みたいに絞りこんで選択肢を狭めていくってことですよね。
情報系の大学生で探索アルゴリズムやったけど、今って高校で習うのか
動画いつも拝見しています。
私、土木学会という学会の委員会で建設業界への情報発信をしています。
ヨビノリの動画を見て、本来建設分野の主軸になる数学や物理の大切さ面白さを考えてもらいたいなと考えているところです。
コラボなどできないかご相談させてください。よろしくお願いします。
恥ずかしながらソートという言葉の意味を初めて理解できました！
新しいことを知れるのは楽しいです
古畑任三郎の存在感🧐
棒線がいっぱい並んでてピロピロ鳴りながら色んなソートしてく動画好きなんだがわかる人おる？
二分探索はノードの形で習いましたｗ
ヨビノリさん、競プラーになってくれ！
アルゴリズムの解説もっとお願いー！
数学おもろしすぎ
犯人捜しのたくみさんからなんとなく古畑任三郎みを感じた
古畑警部は多くても2回で真犯人当てちゃってるからなあ
@@sakakkiedx5052
古畑「警部"補"なんですぅ」
一般的に割り算は低速ですが、2のn乗で割るのは右にnビットシフトするのと同じなので問題にならないですね
ずんだもんさんが解説する任意の自然数を2つ選んだ場合円周率が求まるっている動画でもこの2分探索が使われているのかなぁ
Q＊に合わせてのアップだったらアツい
高速フーリエ変換を使ったハンマリング試験のデータ解析のときにこういうのあったな。
頭悪かったんで当時は何言ってるのかよく理解できなかったけど…
今なら何となく分かる。
あー最近考えてたことだ！
誕生日が7/1より前かと聞かれたら、12月生まれで7月にはまだ誕生日来てないから前だと答える思うけど、他の人はどうなんだろ？
14:30 今日の学び
高一、情報の授業ないけど、この動画面白いなーって見てたら、東進の情報模試でまんまこれ出た
モグライダーにそんなネタがあったのか…このアルゴリズム使った身近な例のアキネイターと書き間違えてるのかと思った😅
👍
14:12 誕生日の話、1年の真ん中は7月2日だなと思った
完璧なランディングに脱帽！世界がスッキリ見えてきます。感謝！
あぁそういえばこの人、理系ドレミの人じゃなかったわ
モグライダーの、さそり座の女の漫才を思い出した
もうやってるかも知れませんがクイックソートもお願いします
二分探索の授業わかりやすかったです！
線形探索よりだいぶ探索時間が早いそうですね。
900とかの宛先に50づつに分けてメールを送る時、問題あるアドレスが一つどこかにあるタメ送れなくなったので、二分探索のようなことしていました。改めて役に立つ授業ですよ🎉
鶴崎さんのモグライダーのネタ解説を思い出しました…w
ロックマンエグゼやった子供たちが無自覚に知ってるやつじゃん！
二分法、工学系の大学2年生が今やってますね
スマホの探索でもワンチャン使えないかな
「トイレ行ったときじゃない？」
「そのときは確実にあった」
「飲み物を取りに行ったときとか？」
「その時にはもうなかったかも」
みたいな
それ線形
書類で二分探索する時、並べ替えた書類はソーっト運ばないといけない
バイナリーソートですね。情報処理系の資格試験の初歩にあるテーマです。
全然関係ないけどラプラス変換の講義ほしい
ﾖﾋﾞ畑任三郎ひさしぶり！
二分探索まじうれしい！
これ俺の誕生日なかなか当てられんのやないか
数学的に正しいことが必ずしも正解ではないということがわかりました
年齢だと上限分らないから地雷踏みかねない
高一の頃部活でやったわ
文系だけど好きなんだよな
先生これかも宜しくお願いいたします。
アルゴリズム系の動画いっぱい欲しいです！
とうとう情報まで手を出したか！
ニ分探索楽しいわかりやすい解説でしたね♪~
バイナリーサーチの弱点は冒頭の説明にあるようにデータがソート済みでなければならない点ですね。
データはランダムな値で与えられることが多いので線形探索的なバブルソートしないとならない💦
入力長に対して準線形時間のソートアルゴリズムがいくつか知られています。(heap sort や merge sort など)
一般に広く使われているプログラミング言語の標準ライブラリでは、先述の merge sort や quick sort、加えてそれらの派生である introsort, timsort などが実装に用いられています。これらは実用上非常に高速です。
つまりソートアルゴリズムの効率化がカギと
ソートを使わないで使用する例として、詐欺がある。
例えば、スポーツの勝ち負けを、「次に勝つのは、こっちだよ。」と言い続けば、本当に勝つのでは？
と、信じてしまう。
で、基本的にソートをするためには、最低でもO(nlogn)の時間計算量が必要になるので、どうやっても遅いんですよね
なので、一般的に二分探索は「挿入がほとんどない場合には強い」んですよね
逆に、挿入が多発するなら線形探索を毎回かけたほうが、全体効率が良くなることが多くなります
@@mh35jp そもそも挿入が多発する環境ならば array-like に固執せず、(乱択)平衡二分探索木などの挿入に強いデータ構造を使うことを視野に入れるべきかもしれませんね。(もちろん実装コストや定数倍とのトレードオフにはなりますが。)
文系の大学生が本当に0からプログラミングを始めるとき、何から始めれば良いですか？
アルゴリズムの勉強からだね。
プログラミング言語には得意分野があるので（基本的には「この部分をもっと簡潔に書きたい」という動機により新しいプログラミング言語が生まれるため）、まずは学ぶ目的を明確にして、プログラミング言語を選ぶ基準を決めるのが大切です。
@@人生パラドックス ありがとうございます！
蟻本が気になっていたので読んでみます
@@あうら-g2j 選ぶ基準すら備えてないので色々読んでみます！ありがとうございます
@@MattK-p8lまずは、自分の研究などの役に立てたいのか、他の人に使ってもらうためのものを作りたいのか（仕事含む）、コンピューターを隅から隅まで弄り倒したいのか、プログラミングや情報科学にまつわる様々な理論や知識を知りたいのか、くらいの大雑把な基準で大丈夫ですよ！
そこが決まったらもう少し詳しい基準を考えましょう。
逆関数が分らない関数の値を計算する時に使いました。(^^)
でも後で逆関数が見つかってガッカリしました。(-_-;)
5の書き順間違ってるよ
唐突ですが、ヨビノリたくみさんってイエス・キリストの再臨ってご存知ですか？聖書を読むともうすぐ来るみたいで私、それすごい楽しみにしてるんですよ！世界中の皆が集まる時なので！是非その時ヨビノリたくみさんとも会いたいです！