凡愚な僕

理系大学生の雑記と備忘録

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

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




二分探索とは

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

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

また、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) <= 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)) [秒]
110
10103.321928
1001006.643856
5005008.965784
100010009.965784
5000500012.287712
100001000013.287712
500005000015.609640
10000010000016.609640
50000050000018.931569
1000000100000019.931569

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

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

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

グラフの作成にはnumpypyplotを使用します。

%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()

グラフにすると効率の違いがよくわかります。

二分探索は非常に優れたアルゴリズムであることが確認できました。

すげ~。

関連記事