【競プロ】ソートされた2次元行列から要素を探し出す3通りの方法 - Qiita

本記事では，ソートされた行列から特定の要素を探し出すアルゴリズムを3通り紹介します．ソートされた行列とは ある要素より右側にある数字はその要素以上 ある要素より下側にある数字はその要素以上 を満たすもので，例えば下の図のような行列です． 行列のサイズは$h*w$とします．この中に例えば「8」があるかどうかを判定し，あればそのインデックス（座標）を返すことが目標です（複数ある場合はどのインデックスを返してもいいものとします）． まず1次元配列のおさらい まず，ソートされた1次元の配列から特定の要素を探索する場合,全要素を一つずつ調べていると$O(n)$時間（$n$は配列の長さ）かかりますが，2分探索によって$O(\log n)$にできることが一般的に知られています．Pythonでは$bisect.bisect\_left()$などを使えば何も知らなくても勝手にできてしまいます． import