(ミーハーアルゴリズム)まずは二部探索から
概要
アルゴリズム大事だなと思って体系的に学ぼうと思ったど素人がまずは二部探索からまとめていく。
隔週くらいで習慣的にアルゴリズムに触れる。（知らんけど）
説明
定義
探索処理の前に配列をまたはリストを整列、整列された集まりの中の特定の要素を効率的に探索するアルゴリズム。
フロー：
- 配列の最初の要素0をlow, 配列の最後の要素len(N)をhighとし、探索範囲を定義
- 中央のインデックスを定義
mid = (low+high)/2 - midの位置が一致するかの確認
a.一致：この要素の位置を答えとして返却。
b. midの値が探している要素より小さい場合:lowをmid+1に
c. midの値が探している要素より大きい場合：highをmid-1に
4.lowがhighより大きくなるまでステップ2, 3を繰り返す。
計算量：
O(logN)
フローにもある通り、この探索が必要なステップ数は,len(N)のリストを2で何回割るかどうかよる。
n回割ったとするとデータ数Nはn * 2 = Nと表せる。
これを変形させると、log(n * 2) = log(N)
n = log(N) = logNとなる。
n * 2 = N
log[2](n * 2) = log [2] (N)
n = log[2](N) = logN
O(logN)
例
説明のフローをコードに落とし込むと以下の様になる。
def binary_search_example(arr, target):
"""
二部探索アルゴリズムを説明するための例関数
1. 配列の最初の要素0をlow, 配列の最後の要素len(n)をhighとし、探索範囲を定義
2. 中央のインデックスを定義 ```mid = (low+high)/2```
3. midの位置が一致するかの確認
a.一致：この要素の位置を答えとして返却。
b. midの値が探している要素より小さい場合:lowをmid+1に
c. midの値が探している要素より大きい場合：highをmid-1に
4.lowがhighより大きくなるまでステップ2, 3を繰り返す。
"""
# step1:探索範囲定義
low, high = 0, len(arr) - 1
# 4. 2, 3のループ
while low <= high:
# 2.中央インデックス定義
mid = (low + high) // 2
# 3.midの位置が一致するかの確認
# a.一致
if arr[mid] == target:
return mid
# b. midの値がtargetより小さい
elif arr[mid] < target:
low = mid + 1
# c.midの値がtargetより大きい
else:
high = mid - 1
# 存在しないなら-1返却
return -1
arr_test = [1, 2, 3, 4, 5, 6]
target_test = 4 # anser: 3
index_found = binary_search_example(arr_test, target_test)
print(f"対象配列の要素番号は{index_found}です")
演習
AIZU ONLINE JUDGE -ALDS1_4_B:Binary Search
基本の二分探索のtargetが配列になったのでwhileの外側でループさせて各要素をtargetとして定義してあげれば良い。
"""
[AIZU ONLINE JUDGE -ALDS1_4_B:Binary Search](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)
二分探索を用いて長さqの配列Tに含まれる整数の中で長さnの配列Sに含まれるものの個数Cを出力
出力
C
を１行に出力してください。
制約
Sの要素は昇順に整列されている
n≤100,000
q≤50,000
0≤Sの要素≤109
0≤Tの要素≤109
Tの要素は互いに異なる
"""
n = input()
S = list(map(int, input().split()))
q = input()
T = list(map(int, input().split()))
C = 0
for target in T:
S_low = 0
S_high = int(n) - 1
while S_low <= S_high:
mid = (S_low + S_high) // 2
if S[mid] == target:
C += 1
break
elif S[mid] < target:
S_low = mid + 1
else:
S_high = mid - 1
print(C)
今回のアルゴリズム問題とは少しズレるが、pythonならば標準ライブラリのbisectライブラリを用いて効率的に二分探索を行った方が良い。
"""
[AIZU ONLINE JUDGE -ALDS1_4_B:Binary Search](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)
二分探索を用いてTに含まれる整数の中でSに含まれるものの個数Cを出力
"""
import bisect
n = input()
S = list(map(int, input().split()))
q = input()
T = list(map(int, input().split()))
C = 0
for target in T:
index = bisect.bisect_left(S, target)
if index != len(S) and S[index] == target:
C += 1
print(C)
長さnの配列Sに対して二分探索を配列Tの長さq分を行うので計算量はO(qlogn)である。
実例
二分探索は現実社会でもコンピュータグラフィックスや金融、gitなどさまざまな製品、業界に用いられており、コンピュータグラフィックスなどで言うレイマーチングにて、物体との交差点をより正確に見つけるために使用されたりしている。
チェックリスト
- 二分探索とはと聞かれて定義を言えるか
- フローがパッと湧くか
- 使い所がわかっているか
備考
手始めに基本のきだと思っている二分探索をまとめさせていただきました！
アルゴリズムがイメージつく様な記事になっていたら幸いです！
二分探索とは言っても色々パターンあるので今回は本当にベーシックな二分探索を取り上げました。
振り返った時にこのまとめをどう感じるかが楽しみです...
参考文献
Discussion