これでマスター二分探索編〜AtCoderを戦うために典型的な問題を徹底マスターしよう！[競プロ解説]〜
はじめに
初めまして。
普段AtCoderにPythonで参戦しているハチです。
今回は、二分探索について初心者でも一から分かりやすく解説していきたいと思います。
実は僕自身、AtCoder歴は現時点で2ヶ月ほどで、まだまだ初心者です。ですが、初心者だからこそ分かる苦悩や引っ掛かりポイントがあると思います。
そこで、自分と同じようにAtCoder初心者でもこれを読めば「二分探索」について理解できるような記事を書けたらと思います。
二分探索とは？
まずは、二分探索とは何なのかを説明します。
そこで、二分探索の定義を示したいと思います。定義ですから、読んでも正直よく分からないな、と思う方がいるかもしれません。
それでも大丈夫です。とりあえず読んでみましょう。
二分探索とは、検索する問題を半分に分割しながら解を探しだすアルゴリズムです。
出典は複数の方がいいですから、もう一つ「二分探索とは何か」についての定義を紹介します。
二分探索とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。
こちらの定義からは、先ほどは説明されていなかった「ソート（整列）済みのデータ群」という文言が含まれています。
つまり、二分探索では昇順、もしくは降順にソートされた配列を用います。
ソートされていないデータ群を入力として与えられた場合は、まずはソートする必要があります。
定義を読んだけど、やっぱりよく分からない！という方は、以下の動画を見てみることをお勧めします。
二分探索についてとても丁寧に分かりやすく解説している動画になります。
二分探索ってどうやるの？
例えば、以下のように、小さい順(昇順)に並んでいる配列について考えます。
今回、ハムが大好きなハコ太郎くんは「86」という数字を探しています。
ハコ太郎くんは単純に１番目から８番まで順に箱を開けて「86」を探すこともできます。
しかし、ハコ太郎くんは「とっとことっとこ」と急いでいるので、出来るだけ箱を開けずに「86」という数字を見つけたいと考えているようです。
じゃあ、どうすれば出来るだけ箱を開けずに「86」という数字を見つけられるでしょうか？
そこで登場するのが「二分探索」という考え方です。
二分探索は、以下の３ステップで成り立っています。
step1. 真ん中の箱を開ける。
step2.
(真ん中の箱に入った数字)＝(探している数字)の場合、終了。
(真ん中の箱に入った数字)＜(探している数字)の場合、探す範囲を右半分に絞る。
(真ん中の箱に入った数字)＞(探している数字)の場合、探す範囲を左半分に絞る。
step3. これを、「(真ん中の箱に入った数字)＝(探している数字)」となるまで続ける。
二分探索ってなんか難しそう、そう思っていたあなたも、
「なんだそんなもんかwただビジュアルが怖いだけで中身は優しいヤンキーじゃん！」と思ったに違いないでしょう。
本当にそうなんです！私も最初の頃は「なんか難しそう」と思っていましたが、「とても簡単」でした。
ここまで理解できたら、あなたもみんなに「おれ二分探索って知ってるけど、お前知ってる？」と言ってみて下さい。私は知りませんがw
二分探索の計算方法
ここからは、中央値の計算方法について説明していきたいと思います。
「ちょ待てよ。どうしてここで中央値の計算方法について説明するんだよ」
とまるでキム◯クのように言いたくなったあなた。
中央値の計算方法について説明する理由は、
二分探索では、この「最大位置」と「最小位置」を更新していく処理がメインディッシュとなるからです。
そして、中央値の計算方法は次の通りになります。
最小位置＋(最大位置ー最小位置)/2
今回冒頭で示した図で言うと、最初は
1＋(8ー1)/2＝４
となります。
二分探索の基本コードって？
では、実際に二分探索の基本コードを見てみましょう。
コードの説明
N 個の値が小さい順に並んだ配列 [A1,A2,…,AN]に対して、この中から値 xを見つける。
最初から順に見ていくと計算量 O(N)かかりますが、
二分探索を使うと計算量 O(logN)で見つけることができます。
なななんと、イイんでしょうか？！
値 x が配列 A のどの位置にあるか（なければ -1 を返す）を返す Python プログラムとなります。
#二分探索の基本コード
def binary_search(N, A, x):
l=0
r=N-1 # A[l], A[l+1], ..., A[r] が探索範囲
while r-l+1>=1: # 探索範囲の長さ r - l + 1 が 1 以上のあいだループする
m=(l+r)//2 # (l + r) / 2 を小数点以下切り捨て
if A[m] == x:
return m
if A[m] < x:
l = m + 1
if A[m] > x:
r = m - 1
return -1
#配列の長さ
n=int(input())
#配列A
a=list(map(int,input().split()))
#見つけたい値
x=int(input())
#関数を実行
binary_search(n,a,x)二分探索の基本コードを実際に動かしてみよう！
実際に上の二分探索の基本コードを実際に動かしてみましょう。
VSCodeやGoogle ColaboratoryなどPythonのコードを動かせる環境に上のコードをコピペして、
return mという部分を
print(m)というコードに置き換えてみて下さい。
今回の入力は、先ほども示した図の配列を用います。
具体的には、長さ8で、[18,22,30,45,47,51,86,97]
のような配列です。
配列で、ハコ太郎くんが探していた「86」が添字表示でどこに存在するのかを調べたいと思います。
入力は以下のようになります。
8
18 22 30 45 47 51 86 97
86
出力は、「6」となったはずです。ハコ太郎くんは無事に「86」を見つけられたでしょうか？(なぜハコ太郎くんがそこまでして「86」を見つけ出したいのかは未だ分からぬ疑問ですが)
今回のような、配列の要素数が少ない場合は計算量を気にする必要はありませんが、要素数が非常に多いような場合ですと、今回のような「二分探索」が有効になってきます。
あなたもこれで立派な「二分探索マスター」です！
例題
今回は、例題としてAtCoderの問題を解いてみましょう。
解説
二分探索の基本コードを少し変えるだけでこの問題が解けます。
解答コードは以下のようになります。
#二分探索の基本コード
def binary_search(N,A,k):
#求める値(初期値は不可能な場合)
ans=-1
l=0
r=N-1 # A[l], A[l+1], ..., A[r] が探索範囲
while r-l+1>=1: # 探索範囲の長さ r - l + 1 が 1 以上のあいだループする
m=(l+r)//2 # (l + r) / 2 を小数点以下切り捨て
if A[m]==k:
ans=m
break
if A[m]>k:
r=m-1
ans=m
if A[m]<k:
l=m+1
print(ans)
n,k=list(map(int,input().split()))
#配列A
a=list(map(int,input().split()))
#関数を実行
binary_search(n,a,k)その他コラム
「bisect」という、「二分探索」を利用することで効率よく、リストをソートされた状態に保つことをサポートするためのPython標準ライブラリがあるようです。
練習問題
今回は、「二分探索」について初心者でも分かりやすいように解説しました。
しかし、学校と同じように、どれだけ真面目に講義を受けてもテストでは満点を取れない、太刀打ちできない、と言ったことがあると思います。そこで、ここでは「二分探索」の考えによって解くことのできる「二分探索問題集」を紹介したいと思います。
ここで紹介した問題たちをマスターできれば、二分探索なんて怖くない！二分探索どんとこい！二分探索楽しい！と思えるのではないでしょうか。
[二分探索を練習できる問題集]
二分探索についての内容はこれで以上です。
ここから先は超初心に向けての内容ですので、読まなくても全く問題ないです。
AtCoder初心者が、AtCoderのレーティングを上げるためにはこれから何をしたら良いのかについて書きました。
AtCoderの典型問題(アルゴリズム)とは
今回の記事でなぜ「二分探索」を取り上げたのかについて説明したいと思います。
理由はズバリ、
AtCoderでレーティングを上げたい！C問題まで解けるようになりたい！と思っている方は、AtCoderで典型問題と言われているような以下のような解き方をマスターすることが重要だと思っているからです。
では、なぜそれが重要なのか？それは、以下に記した典型問題(アルゴリズム)が、大学受験における、「複素数平面」「2次曲線」「極限」「微分法」「積分法」のようなものだからです。
これらを使った解き方の基本をマスターすれば、それなりに点数が取れる、といったある種のボーダーラインとなります。
◎全探索
・二分探索
・bit全探索
◎バケット・連想配列
◎区間分割・連長圧縮
◎グラフ
◎累積和
・数学的解法(幾つか考えるコツがある。偶奇についてなど)(これから執筆予定)
上の中で、◎がついた項目は、(通称)鹿本にかなり優しく丁寧に解説されている典型問題(アルゴリズム)です。これらの典型問題(アルゴリズム)は、ぜひ鹿本を買ってマスターしてください！(けんちょんさんという方が書かれた良書です。C++、Pythonでの実装例が書かれています。)
他にもたくさんありますが、初心者の方はひとまず初心者から脱却するために、上のような典型問題(アルゴリズム)をマスターすれば良いかと思います。ここまで出来れば、あなたも茶コーダーの仲間入りを無事果たすことができると思います。
超初心者に向けて(これから何をしたらよいか)
AtCoder初心者で、何をしたら良いのか分からない方には、以下の本をお薦めします。
こちらは、AtCoderの典型問題についてかなり優しく丁寧に解説されています。また、それぞれの典型問題(アルゴリズム)ごとに例題、練習問題が豊富に紹介されています。かなり鍛えられる良書です。
こちらは、私が初めて手に取ったAtCoder本です。後半の方はかなり難易度が高く、一つ目の本を解くことに注力しました。ただ、AtCoderで必要な入出力方法についてはこちらの本で学びました。
おわりに
ここまで読んで下さって本当にありがとうございました。
さて、どうでしたか。「二分探索」をマスターすることはできましたか？
もしここが分からない、ここをこうしたらもっと分かりやすい記事になるんじゃない？と思った方、その他何でもコメントを下さると嬉しいです。より良い記事を書くための参考、モチベーションにしたいです。
これからは、冒頭でも示したAtCoderで典型問題と言われているような項目のうち、「数学的解法(幾つか考えるコツがある。偶奇についてなど)」について今回と同じような形で書いてみたいと思います。
ですので、今回分かりづらいと感じた箇所があればコメント等を参考に改善、修正をしながら執筆したいと思います。これからもよろしくお願いします。
今回の曲はこちら。最近漫画「ナルト」を読んでいます。ナルトってめっちゃ面白いな。
岸本先生尊敬します。
参考文献
(スペシャルサンクス)
(その他)
ゆるぼ AtCoder公式コンテストで二分探索の問題で出来るだけシンプルな奴
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) September 3, 2021
よろしければサポートよろしくお願いします！いただいたサポートはクリエイターとしての活動費として使わせていただきます！