二分探索の概要
- 探索したい値とデータの中央の値を大小比較し、半分に絞り込んでいく
- 探索の対象となるデータが昇順にソートされている必要がある。
- 計算量はO(logn)
二分探索の実装
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
x = [1,2,3,4,5,6,7,8,9] def binary_search(x,y): min = 0 max = len(x)-1 while min<=max: middle=(min+max)//2 if x[middle]==y: return middle elif x[middle]<y: min=middle+1 else: max=middle-1 return mid print(binary_search(x,30)) |
二分探索の実装(補足付)
こちらは前述のコードに補足をつけたものです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
x = [1,2,3,4,5,6,7,8,9] def binary_search(x,y): #関数を定義。 min = 0 #リストxの最小値1はx[0]で表せる。最小値の要素番号である0をminに代入 max = len(x)-1 #リストxの要素数len(x)は9、最大値9の要素番号はリストの要素数-1で表すことができ、maxに代入。 while min<=max: #minがmaxより小さい間は繰り返し処理を行う。(以下は1回目の実行時について記載。) middle=(min+max)//2 #変数middleにmin+maxを2で割った値(真ん中の要素番号)を代入する。(1回目は(0+8)//2=4) if x[middle]==y: #x[4]、つまり5が探索したい値と一致した場合 return middle #middle(要素番号である4)を返す elif x[middle]<y: #x[4]、つまり5が探索したい値よりも小さい場合 min=middle+1 #minを4+1=5にする。(中央の値より1大きい値を次の最小値とする。) else: #x[4]、つまり5が探索したい値よりも大きい場合 max=middle-1 #maxを4-1=3にする。(中央の値より1小さい値を次の最小値とする。) return mid #探索したい値がリストx内にない場合はmidを返す。 print(binary_search(x,9)) #関数binary_search()実行。探索する対象としてリストx、探索したい値として9を渡している。 |
二分探索でAtcoderに挑戦(ABC 212 C問題)
問題:Atcoder Beginnger Contest 212 C問題
問題については公式サイトをご覧ください。
解答についてはこちらの記事で書きました。
解法1:bisectを用いる
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import bisect n,m = map(int, input().split()) a = list(map(int, input().split())) a.sort b = list(map(int, input().split())) b.sort() ans = 10**9 for i in a: c = bisect.bisect(b,i) ans = min(ans,abs(i-b[c-1])) if c<m: ans = min(ans,abs(i-b[c])) print(ans) |
この記事は二分探索についてのものですが、bisectというライブラリが作成されています。
自身で実装する必要がないので、実務やAtcoderで二分探索を使うことがあればこちらを利用した方が早いです。
解法2:自分で二分探索を実装して解く
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
def Binary_search(x,y): min=0 max=len(x)-1 while min<=max: mid=(min+max)//2 if x[mid]==y: return mid elif x[mid]<y: min=mid+1 else: max=mid-1 return mid n,m = map(int, input().split()) a = list(map(int, input().split())) a.sort b = list(map(int, input().split())) b.sort() ans = 10**11 for i in a: c=Binary_search(b,i) ans=min(ans,abs(i-b[c])) ans=min(ans,abs(i-b[c-1])) if c!=m-1: ans=min(ans,abs(i-b[c+1])) print(ans) |
自身で実装する必要はないのですが、せっかくなので自分で二分探索を実装した上で解いてみました。
意味があったかはともかく、bisectと今回の記事で書いた二分探索のコードは異なる点があることがわかりました。
bisectではリスト内に探索対象となる値が含まれていない場合、mid+1の要素番号を返しているように見えます。
一方、こちらの記事で実装した二分探索ではmidの要素番号を返します。
細かい違いですが、同じ二分探索を実装する場合でも人によって違いがあることがわかりました。
ライブラリを利用して別の問題を解いたり実装を行う際は、ライブラリの中身が異なることで、それ以外の部分もコードが異なってきそうです。
現在の私の仕事でコードを書くことは少なく、せいぜい自身の業務効率化のためにちょっとしたプログラムを書く程度ですが、もし同僚と一緒にコードを書く機会に恵まれた場合は、注意したいと思います。
参考書籍
こちらの書籍を参考にさせて頂きました。
今回の記事では書ききれていない詳細な説明がある点、二分探索以外の探索手法についても体系的にまとめられている点、Atcoderを解いていく上で必須の計算量についても解説されている点など、Pythonの学習者にとっては購入して損はないと考えています。
ネットに記載されている情報もこちらの本を参考にしていると思われる記事もあります。ネット全盛の現代でも、体系的に情報を得るためには書籍は高い価値を持っていると思います。
競技プログラミングに取り組む上では蟻本と呼ばれるこちらの書籍が推奨されていますが、言語はPythoではなくC++が使われています。C++はPythonよりも早いということで、AtcoderでもC++を使用している方が多いですが、Pythonしか使ったことのない私には難しく、先ほど記載した本で勉強しています。
コメント