コンピューター · 二分探索
100万の名前から1つを、どうやって20回で見つけるの？
この動画で見られること
電話帳に百万人の名前が、五十音順に並んでいます。一つずつ調べたら、百万回見ることになるかもしれません。もっとうまくできないでしょうか？ ちょうど真ん中を開きます。探している名前はもっと後ろなので、前半はまるごと消えます。残りは五十万。残りの真ん中を開いて、また半分にします。さらにもう一度。一回見るたびに、残りの半分を捨てられます。二十回半分にすれば、百万がたった一つになります。二の二十乗は、百万をほんの少し超えるからです。十億人なら？ あと十回見るだけです。
