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

# 目次
[1 二分探索とは](#1-二分探索とは)
[2 言語](#2-言語)
[3 実装](#3-実装)
　[3-1 全探索](#3-1-全探索)
　[3-2 二分探索](#3-2-二分探索)
[4 考察](#4-考察)

#1 二分探索とは

><a href="https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88">ソート</a>済みの<a href="https://ja.wikipedia.org/wiki/%E3%83%AA%E3%82%B9%E3%83%88">リスト</a>や<a href="https://ja.wikipedia.org/wiki/%E9%85%8D%E5%88%97">配列</a>に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

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

<a href="https://atcoder.jp/contests/abc146/tasks/abc146_c">ABC146 - C問題</a>を例に、全探索と二分探索の2つの手法で問題を解いて、具体的な違いを確認してみましょう。



#2 言語
Python



#3 実装

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

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



##3-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()
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 考察
では、具体的な計算量の違いを以下で確認していきます。

<!-- wp:table {"className":"is-style-stripes"} -->
<figure class="wp-block-table is-style-stripes"><table><tbody><tr><td><strong>データ量 n</strong></td><td><strong>全探索 O(n)</strong></td><td class="has-text-align-left" data-align="left"><strong>二分探索 O(log_2(n))</strong></td></tr><tr><td>1</td><td>1</td><td class="has-text-align-left" data-align="left">0</td></tr><tr><td>10</td><td>10</td><td class="has-text-align-left" data-align="left">3.321928</td></tr><tr><td>100</td><td>100</td><td class="has-text-align-left" data-align="left">6.643856</td></tr><tr><td>500</td><td>500</td><td class="has-text-align-left" data-align="left">8.965784</td></tr><tr><td>1000</td><td>1000</td><td class="has-text-align-left" data-align="left">9.965784</td></tr><tr><td>5000</td><td>5000</td><td class="has-text-align-left" data-align="left">12.287712</td></tr><tr><td>10000</td><td>10000</td><td class="has-text-align-left" data-align="left">13.287712</td></tr><tr><td>50000</td><td>50000</td><td class="has-text-align-left" data-align="left">15.609640</td></tr><tr><td>100000</td><td>100000</td><td class="has-text-align-left" data-align="left">16.609640</td></tr><tr><td>500000</td><td>500000</td><td class="has-text-align-left" data-align="left">18.931569</td></tr><tr><td>1000000</td><td>1000000</td><td class="has-text-align-left" data-align="left">19.931569</td></tr></tbody></table></figure>

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

これらをグラフで確認してみます。
グラフの作成には`numpy`と`pyplot`を使用します。

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

<!-- wp:image {"align":"center","id":112,"sizeSlug":"large"} -->
<div class="wp-block-image"><figure class="aligncenter size-large"><img src="https://jorihige.files.wordpress.com/2020/06/image.png?w=386" alt="" class="wp-image-112"/></figure></div>
<!-- /wp:image -->

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