【Code Kata 翻訳 その2】空手チョップ！

原文はCode Kata Two - Karate Chopです。

Code Kata Two - 空手チョップ！

バイナリチョップ(要するに、二分探索法)では、順番に並んだ値の配列の中での、目的の値の位置が分かります。
値を調べる度に考慮する値の件数を半分にしていくので効率的です。
最初のステップで、目的の値は、配列の前半にあるのか後半にあたるのかが決まります。次のステップでは、先ほどの前半or後半の中の半分についてだけ考えればよく、更に前半と後半に分かれます。目的の値が見つかるか、木を全て探索し終われば手順は完了です。二分探索法はCSの中で一番好きな講義です。

このカタは明解です。あなたの好きなプログラム言語とテクニックを使って、二分探索法ルーチンを実装して下さい。ただし、後述の仕様に則って下さい。
実装できた次の日には、全く違うテクニックを使ってもう一度実装してみてください。次の日も、次の日も。。まるで異なる二分探索法の実装が5つできるまで続けて下さい。(例えば、古典的な繰り返しアプローチや、再帰処理や、配列の中を回す関数、などが考えられます)

目的
このカタは3つのゴールに分けられます。

1. それぞれのアルゴリズムをコーディングすることによって、出会った失敗の種類を記録しておくことができます。二分探索法は境界条件や植木算エラーを鍛えるのに適した問題です。日が経つにつれ、これらの失敗を起こす頻度が少なくなっていくと思います。(そしてそれは、一つのテクニックから学んだのでしょうか、それとも複数の異なるテクニックでコーディングしたからでしょうか？)


2. あなたが選択したテクニックの優劣について分かっていますか？本番用のコーディングに最も適しているのはどれでしょうか？書いていて一番面白かったコードはどれでしょうか？プログラムを動かすのに一番苦労したのは？そして、これらの問いについて、「なぜそうなのか」を考えて見てください。


3. 5つもの二分探索法のアプローチを考えるのはかなりきつかったでしょう。4つ目と5つ目のアプローチはどのようにして考え付きましたか？突飛なニューロン脳細胞を発火させるために、どんなテクニックを使いましたか？

二分探索法の仕様
二分探索法のメソッドを記述するのには「目的の値」と「ソート済みの整数の配列」の2つが必要です。このメソッドは目的の値が配列の何番目に位置するかの整数(ゼロベース)を返します。が、目的の値が配列の中になかった場合には「-1」を返却します。論理的にこんな感じで記述できるでしょう。

chop(int, array_of_int) -> int

配列の要素数は100,000未満でよいコトとします。このカタでは、処理速度やメモリのパフォーマンスについては考慮しません。十分なRAMで十分な速度でアルゴリズムが動いているというコトにしておいてください。

コードカタの筆者が実装するときに使用したテストコードです。自由にケースを追加してくれていいです。このテストでは、配列の添え字が0から始まることを担保しています。このテストケースをあなたの選択した言語に合う形にするには、グローバル検索とグローバル置換が何回か必要になると思います(たまたまRubyを選択していたら、その限りではないですが)

def test_chop
assert_equal(-1, chop(3, []))
assert_equal(-1, chop(3, [1]))
assert_equal(0,  chop(1, [1]))
#
assert_equal(0,  chop(1, [1, 3, 5]))
assert_equal(1,  chop(3, [1, 3, 5]))
assert_equal(2,  chop(5, [1, 3, 5]))
assert_equal(-1, chop(0, [1, 3, 5]))
assert_equal(-1, chop(2, [1, 3, 5]))
assert_equal(-1, chop(4, [1, 3, 5]))
assert_equal(-1, chop(6, [1, 3, 5]))
#
assert_equal(0,  chop(1, [1, 3, 5, 7]))
assert_equal(1,  chop(3, [1, 3, 5, 7]))
assert_equal(2,  chop(5, [1, 3, 5, 7]))
assert_equal(3,  chop(7, [1, 3, 5, 7]))
assert_equal(-1, chop(0, [1, 3, 5, 7]))
assert_equal(-1, chop(2, [1, 3, 5, 7]))
assert_equal(-1, chop(4, [1, 3, 5, 7]))
assert_equal(-1, chop(6, [1, 3, 5, 7]))
assert_equal(-1, chop(8, [1, 3, 5, 7]))
end