二分探索法について

昨日のAtCoder Beginner Contest 174（ABC174）を復習しました。そのうちE問題は二分探索法の典型問題であったため、その方法についてまとめます。本ページでは、E問題の解答自体は扱いません。解答は他の問題と合わせて後日まとめて公開したいと思います。

では、いきます。

問題

ABC174E問題はこんな感じです。原文はこちらからお願いします。
https://atcoder.jp/contests/abc174/tasks/abc174_e

N本の丸太（長さは、A1,A2,...,An）がある。
合計K回丸太を任意の位置で切る。
（例：5cmの丸太を1.5cmと3.5cmに切る、これで1回）
丸太の長さの最大値が最も小さくなるように切ったときの最大の長さは？

二分探索法を使えば楽に解けるので、その方法について説明します。

二分探索法って？

何回も二分探索法と難解な言葉を並べましたが、簡単に言ってしまえば、「high or low」を繰り返すやつです。

Aさんが1~100のうち一つ数字を思い浮かべる。Bさんが数字を言って、思い浮かべた数字よりも「高い」「低い」というヒントを出す。どういう風に言えばできるだけ少ない回数で当てられるか。

一番、頭の悪いやり方をすれば、1から順番に100まで言っていけばどんなに運が悪くても100回までに当たります。でも、1~1000000までとかにしてしまうと、なかなかに心が折れます。ヒントを出す方も心が折れます。

では頭のいい人ならどうするかというと、まず真ん中の数を言って、それよりも「高い」「低い」に従って、さらに真ん中の数をいうと思います。1~100までなら、
50、「高い」→75、「低い」→63、「低い」→・・・
と3回の試行で、51~62までの12個に絞れました。続けていけば、答えが出ます。

このように、真ん中の数を言うことで少ない回数で当てられる方法を二分探索(Binary Search)といい、頭の悪いやり方（線形探索 : Linear Search）よりも計算コストが小さく（O(n)→O(log n)）となります。

プログラム

実際に1~100までの数値を当てる、二分探索法のアルゴリズムをプログラムで書いてみます。C++です。

#include <iostream>
using namespace std;

int main(void)
{
 //思い浮かべた数
 int ans;
 cin >> ans;
 
 //何回で当てられたか
 int cnt = 0;
 
 int low, high;
 int mid;
 
 low = 0; //*1
 high = 100;
 
 while(high - low > 1)
 {
   //intで余りを切り捨てる
   mid = (low + high) / 2;
   
   cnt++;
   
   //「高い」「低い」の判定
   if(mid >= ans) //思い浮かべた数が真ん中以下のとき*2
   {
     high = mid;
   }
   else if(mid < ans) //真ん中より大きいとき
   {
     low = mid;
   }
 }

 cout << "思い浮かべた数 : " << ans << endl;
 cout << "二分探索で求めた数 : " << high << endl;
 cout << "探索した回数 : " << cnt; 
}

*1 *2の実装は出力をhighにしているため。
あと、mid == ansでwhileを脱出しても良いと思います。本質ではないので上記のような実装をしてます。 

おわりに

上記の例はとても簡単ですが、少し加えるだけでEの丸太の問題も解けてしまいます。テスト中は、なんだこの問題と思ったけど、本質を見ればなんだこんな問題かー、という感じです。発想というか、問題を解いた経験といいますか、、、ぱっとみて、あー、はいはい、と解けるようになりたいものです。