More than 3 years have passed since last update.

ABC146-C問題で二分探索法を理解する

Last updated at 2021-05-22Posted at 2021-05-14

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

二分探索は資格試験でも度々登場する非常に有名で基本的なアルゴリズムです。
また、AtCoderなどに参加している方がまず学習すべきアルゴリズムでもあります。
ABCのA問題やB問題では全探索(full search)で解ける問題が多いですが、計算量がO(n)であることから多くの計算が求められる問題になるとACを出すことが難しくなります。
それに対して二分探索は計算量がO(log_2(n))と非常に高速に計算処理を行うことが可能です。

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

#2 言語
Python

#3 実装

##3-1 全探索
まずは、全探索で解いてみます。

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です。

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

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回です。
これからわかるように、二分探索は全探索と比較して確かに計算量が小さいことがわかります。

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

データ量 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()

グラフにすると効率の違いがよくわかります。
二分探索は非常に優れたアルゴリズムであることが確認できました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ABC146-C問題で二分探索法を理解する

目次