２分探索

気がつけば２ヶ月が経過していた。。。

どうも最近頭を使っていないことが多いので、
今更ながら「珠玉のプログラミング」という本を移動時に読み中。
その途中で出てきた話で、２分探索は簡単なようでかなりの人がバグを作りこむと書いてあった。

生徒であるプログラマには、好きな言語でこれをプログラム化するよう、２〜３時間与えました。すると、大部分のプログラマは時間内にプログラムできたと言ってきました。それから３０分ほどかけて彼らのプログラムがちゃんと動くかテストします。いくつものクラスで、１００人以上のプログラマを対象に同じことをしてきたのですが、結果はいつもほとんど同じで、９０パーセントのプログラムはバグがあったと言います。
・・・
最初に２分探索の考え方が公開されたのは1946年だったのに、バグなしのプログラムが出版されたのは1962年になってからだったというのです。

うーむ。。。そういえば書いたこと無いけど、そんな難しくないでしょ〜と思って書いてみた。

var olist = new Array(100);
var WshShell = WScript.CreateObject("WScript.Shell");

for(var i = 0; i < olist.length; i++)
{
	olist[i] = i;
}

function serchTwo(list, value)
{
	var x = (list.length % 2 == 0) ? list.length/2 : list.length/2 - 0.5;

	if(list.length == 1)
	{
		if(list[0] == value)
			WshShell.Popup("見つかったー！");
		else
			WshShell.Popup("残念賞！");
		
		return;
	}
	else
	{
		if(list[x] <= value)
			list = list.slice(x);
		else
			list = list.slice(0, x);
	}

	serchTwo(list, value);
}

serchTwo(olist, 100);

再帰を使わない場合は。。。これより面倒そうなので却下。
境界値に問題がないので多分大丈夫なはず。。。
書いてみて思ったけど、何か値を返してこその再帰というイメージがあるので、↑は再帰っぽくないなー。