CodeKata Two -- Karate Chop

コード＝カタ　二分探索を極める。

A binary chop （binary searchのコト），

それは，ソートされた配列から，探したい値のインデックスを求める単調な方法だ。
探したい値が，全体を二分したグループのどちらにあるかに着目する。
この二分する作業を繰り返し，探している値を見つけるか，
配列の中を探し終えたときに，処理が止まる。
効率はまずまずだ。

【問題】
このKataは直球勝負だ。
テクニックや言語は君に任せるから，二分探索を実装してほしい。
そして次の日，まったく違ったやり方で，再び，実装してもらいたい。
こんなことを，その次の日も，そのまた次の日も繰り返す。
合計，5種類の二分探索を実装してみてくれ。
例えば，ひとつは典型的な繰り返し方式のものだったり，
再帰的だったり，処理が関数に切り分けられていのものだろう。

【目的】
1.アルゴリズムを組む中で出会う，エラーの一つ一つに注目してほしい。
二分探索はエラーの宝庫なんだ。多くのバリエーションを作成していくうちに，
エラーに遭遇することが減っていくのを実感するだろう。

2.作ったバリエーションを見比べて見よう。どれが一番実用的か？
作ってて楽しかったか？完成まで大変だったか？
そして，何故そうっだったかを考えよう。

3.実際，二分探索について，5種類のオリジナルなやり方を見出すのは難しい。
どのようにして達成したか，柔軟な発想ができたかを振り返ろう。

【仕様】
二分探索メソッドを作成する。引数は，探したい値と，対象となる配列だ。
戻り値は，探したい値のインデックスまたは-1（見つからなかったとき）。

chop(int, array_of_int) -> int

配列の数は多くないと思っていい。計算時間やメモリ容量は，このKataでは
気にしなくていい。

【試験値】
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

【Ans.1】　基本形。Javaです。

	private int chop(int target, int[] array){
		if(array.length==0){		
			return -1;
		}
		int begin = 0;
		int end   = array.length - 1;
		
		while(begin <= end){
			int mean  = (begin+end)/2;
			if( target < array[mean]){
				end = mean -1;
			}else if(target > array[mean]) {
				begin = mean + 1;         
			}else{
				return mean;
			}
		}
		return -1;
	}

【Ans.1.1】　基本形。Rubyです。

def chop(target, array)
	rem = 0
	while array.size >= 1
		mid = ((array.size-1)/2).to_i
		case target <=> array[mid]
			when 1
				array = array[mid+1,array.size]
				rem += mid+1
			when 0
				return mid+rem
			when -1
				array = array[0,mid]
		end
	end
	return -1
end