エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
ここにツイート内容が記載されます https://b.hatena.ne.jp/URLはspanで囲んでください
Twitterで共有ONにすると、次回以降このダイアログを飛ばしてTwitterに遷移します
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
本記事では,ソートされた行列から特定の要素を探し出すアルゴリズムを3通り紹介します.ソートされた行... 本記事では,ソートされた行列から特定の要素を探し出すアルゴリズムを3通り紹介します.ソートされた行列とは ある要素より右側にある数字はその要素以上 ある要素より下側にある数字はその要素以上 を満たすもので,例えば下の図のような行列です. 行列のサイズは$h*w$とします.この中に例えば「8」があるかどうかを判定し,あればそのインデックス(座標)を返すことが目標です(複数ある場合はどのインデックスを返してもいいものとします). まず1次元配列のおさらい まず,ソートされた1次元の配列から特定の要素を探索する場合,全要素を一つずつ調べていると$O(n)$時間($n$は配列の長さ)かかりますが,2分探索によって$O(\log n)$にできることが一般的に知られています.Pythonでは$bisect.bisect\_left()$などを使えば何も知らなくても勝手にできてしまいます. import