二分探索を復習してみた(Python)
はじめに
- 二分探索について復習してみました
アルゴリズム概要
2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。 2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。 この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。 なお、この手法はデータが整列していることが前提のため、データの変更が多い状況では、その準備のためのソートにかかる時間により、かえって全体の効率が落ちる場合がある。
- アニメーション
主な解法パターン
1_while文で独自実装
# リスト[1,3,4,5,6,7,9,10,13] があるとき、 # 要素の値が6のインデックスは？ def binary_search(list,taget): ''' 要素の値targetのindexを返す関数 ''' result = -1 left = 0 # leftとright（インデックス）を使ってリストの検索部分を追跡 right = len(list) - 1 # はじめは、leftは0, rightはリストの最後のインデックスを設定 while left <= right: # 1つの要素に絞り込まれるまでの間は... center = (left + right)//2 # 真ん中の要素を調べる if list[center] == target: # 真ん中の要素 = targetのとき（目標を検出したとき） result = center # -> そのインデックスを返して抜ける break elif list[center] < target: # 真ん中の要素がtargetより小さかったとき left = center + 1 # -> leftをcenterより右に設定し直す。rightはそのまま elif list[center] > target: # 真ん中の要素がtargetより大きかったとき right = center - 1 # -> leftはそのまま。rightをcenterより左に設定し直す。 if result == -1: return str(target) + "は見つかりませんでした" else: return "要素の値が" + str(target) + "のインデックス=>" + str(result) example_list = [1,3,4,5,6,7,9,10,13] target = 6 example_list = sorted(example_list) binary_search(example_list, target) # -> 要素の値が6のインデックス=>4
2_bisectライブラリ利用
# リスト[1,3,4,5,6,7,9,10,13] があるとき、 # 要素の値が6のインデックスは？ import bisect example_list = [1,3,4,5,6,7,9,10,13] target = 6 bisect.bisect_left(example_list, target) # -> 4
3_めぐる式
# 20 歳以上 40 歳未満であることはわかっている A さんの年齢を 4 回の質問で当てる # 例えば、37歳 def is_ok(arg): # 条件を満たすかどうか？問題ごとに定義 return arg <= 37 def meguru_bisect(left, right): ''' 初期値のleft,rightを受け取り,is_okを満たす最小(最大)のrightを返す まずis_okを定義すべし left right は とり得る最小の値-1 とり得る最大の値+1 最大最小が逆の場合はよしなにひっくり返す ''' while (abs(right - left) > 1): center = (right + left) // 2 print('center: ' + str(center)) if is_ok(center): left = center else: right = center return left meguru_bisect(19, 41) # -> center: 30 # -> center: 35 # -> center: 38 # -> center: 36 # -> center: 37 # -> 37
ABC143_D
問題
* [abc143_d](https://atcoder.jp/contests/abc143/tasks/abc143_d) - difficulty: 671
考え方
三つの不等式をそれぞれ比較するのは遅いのででソートして一つの不等式のみを比較すれば良い a < b < c にしておいて、あとは a + b > c を満たせば良い ナイーブには nC3 通りの選び方を全探索 -> 間に合わない -> 3つのうち、2つ（a, b）を固定して考える a,b を全探索 -> L の中で最初に a+b 以上になってしまうインデックスを求める = c の動ける範囲の右端を求める -> c の動ける範囲がそれによって求まるので、合計していく = c の動ける範囲は、[j+1, k) （bより先、上記で求めた右端より左）
解法
- 1_while文で独自実装
N=int(input()) L_list = list(map(int,input().split())) def binary_search_left(list,target): ''' 配列に対してある数nを配列のソート順を崩さないように挿入するためのindexを返す関数。 同一の数が配列に複数含まれていた場合は最も小さいindexを返す。 ''' result = -1 left = 0 right = len(list) - 1 while left <= right: center = (left + right)//2 if list[center] == target: # 一致した場合 if list[center - 1] == target: # -> その一つ前も一致した場合、rightをcenterにしてもう一周 right = center else: # -> その一つ前は一致しない場合、一番左で一致したということでcenterを返す return center elif list[center] < target: left = center + 1 elif list[center] > target: right = center - 1 return left # 一致したらcenterを返すが（上記）、なければleftのインデックスを返す L_list = sorted(L_list) ans = 0 for a_index in range(0, N): for b_index in range(a_index+1, N): a = L_list[a_index] b = L_list[b_index] c_right_index = binary_search_left(L_list, a+b) if c_right_index > b_index: ans += c_right_index - b_index - 1 else: pass print(ans)
-> TLEするのでライブラリに置き換える
- 2_bisectライブラリ利用
N=int(input()) L_list = list(map(int,input().split())) import bisect L_list = sorted(L_list) ans = 0 for a_index in range(0, N): for b_index in range(a_index+1, N): a = L_list[a_index] b = L_list[b_index] c_right_index = bisect.bisect_left(L_list, a+b) if c_right_index > b_index: ans += c_right_index - b_index - 1 else: pass print(ans)
ABC146_C
問題
* [abc146_c](https://atcoder.jp/contests/abc146/tasks/abc146_c) - difficulty: 740
解法
- 3_めぐる式
a,b, x = map(int,input().split()) def calc_price(n): return a * n + b * len(str(n)) left = 1 right = 10 ** 9 while left <= right: center = (left + right)//2 if calc_price(center) == x: if calc_price(center + 1) == x: left = center else: break elif calc_price(center) < x: left = center + 1 elif calc_price(center) > x: right = center - 1 print(right)
