【Python】ABC146 C問題で二分探索法を理解する

f:id:mizukawa815:20211014085924p:plain
今日はABC146 C問題で二分探索法を理解していくよ～。
基本中の基本のアルゴリズムだから学んでおいて損はないよ思うよ！

二分探索とは
使用言語
実装
- 全探索
- 二分探索
考察

二分探索とは

二分探索とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。

引用元：二分探索（2分探索）とは - IT用語辞典 e-Words

二分探索は資格試験やプログラミングテストなどで度々登場する非常に有名で基本的なアルゴリズムです。

また、AtCoderなどに参加している方がまず学習すべきアルゴリズムでもあります。

ABCのA問題やB問題では全探索(full search)で解ける問題が多いですが、計算量がO(n)であることから多くの計算が求められる問題になるとACを出すことが難しくなります。

それに対して二分探索は計算量がO(log_2(n))と非常に高速に計算処理を行うことが可能です。

ABC146 - C問題を例に、全探索と二分探索の2つの手法で問題を解いて、具体的な違いを確認していきます。

使用言語

Python

実装

全探索

まずは、全探索で解いてみます。

import time

def cost(n):
    return a * n + b * len(str(n))

a, b, x = map(int, input().split())
n_max = 10**9
start_time = time.time()

if cost(1) > x:
    print(0)
    exit()
elif cost(10**9) &lt;= x:
    print(10**9)
    exit()

for n in range(n_max):
    d = len(str(n))
    if cost(n) > x:
        elapsed_time = time.time() - start_time
　　print(n-1)
        print("\n経過時間:{}".format(elapsed_time) + "[秒]")
        exit()</pre>

>>入力
13 48 498974678
>>出力
38382638
実行時間:32.40821957588196[秒]

データnに対する全探索の計算量はO(n)で今回の入力ケースでは、実行時間は約32秒でした。

このまま提出してももちろん結果はTLEです。

二分探索

次は二分探索法を用いて解いてみます。

import time

def cost(n):
    return a * n + b * len(str(n))

a, b, x = map(int, input().split())
n_max = 10**9
start_time = time.time()
bottom = 1
top = 10**9

if cost(1) > x:
    print(0)
    exit()
elif cost(10**9) &lt; x:
    print(10**9)
    exit()

while top - bottom > 1:
    mid = (bottom + top) // 2
    if cost(mid) > x:
        top = mid
    else:
        bottom = mid

elapsed_time = time.time() - start_time
print(bottom)
print("経過時間:{}".format(elapsed_time) + "[秒]")</pre>

>>入力
13 48 498974678
>>出力
38382638
実行時間:0.0[秒]

実行時間は限りなく0に近い値が出ました、ちなみにループ回数は30回です。

これからわかるように、二分探索は全探索と比較して確かに計算量が小さいことがわかります。

考察

では、具体的な計算量の違いを以下で確認していきます。

データ量 n	全探索 O(n) [秒]	二分探索 O(log_2(n)) [秒]
1	1	0
10	10	3.321928
100	100	6.643856
500	500	8.965784
1000	1000	9.965784
5000	5000	12.287712
10000	10000	13.287712
50000	50000	15.609640
100000	100000	16.609640
500000	500000	18.931569
1000000	1000000	19.931569

全探索ではデータ量の増加と共に計算量も増加していることがわかります。

二分探索ではデータ量が増加しても計算量にそれほどの違いがないことがわかります。

これらをグラフで確認してみます。

グラフの作成にはnumpyとpyplotを使用します。

%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

x = np.arange(1,50)
#全探索
f = x
#二分探索
g = np.log2(x)

plt.xlabel("n", size="14")
plt.ylabel("amount of calculation", size="14")
plt.plot(x, y1, label="full search")
plt.plot(x, y2, label="binary search")
plt.legend()