感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

ソートした後で、真ん中付近から調べていくバイナリサーチ

<スポンサーリンク>

イナリサーチについて

イナリサーチとは、二分探索と呼ばれるサーチ方法である。
全体を2つに分け、目的の値が分割点の前後どちらにあるかを判断して、検索範囲を狭めていく。

ただし、こうやって2つに分けて探索するということは、数値がソートされている必要がある。
ソートにも時間がかかるので、バイナリサーチを使うかどうかはある種トレードオフとなる。

一度ソートしたら、後は何回もサーチを行うよ、というときは、最初に一回ソートしておくといい。
ほとんど一発勝負の探索の場合は、ソートするまでもなく、リニアサーチしてもいい。

この辺は、どんな探索要件かによって、選択肢が異なる。

Node.jsでバイナリサーチのサンプルを作ってみる

以下は、Node.jsで配列を使ったりして、バイナリサーチを行うサンプル。

function binarySearch(target, array) {
	var left = 0;
	var right = array.length;
	var mid;
	console.log("ターゲットは!" + target + "ですね!");
	
	while (left <= right) {
		//真ん中の数値(四捨五入する)
		mid = Math.round((left + right) / 2);
		if (array[mid] == target) {
			return mid;
		}
		//targetは真ん中より左には無い
		if (array[mid] < target) {
			left = mid + 1;
		} else {
			//targetは真ん中より左にある!
			right = mid -1
		}
	}
	return -1;
}

var myVar = new Array();

for (var i = 0; i < 100; i++) {
	myVar.push(parseInt(Math.random() * 100));
}
console.log("配列の大きさは:" + myVar.length);

myVar.sort();

//マイケル・ジョーダンの背番号をターゲットにしてみよう。
var target = 23;

var targetIndex = binarySearch(target, myVar);

console.log("targetのIndexは:" + targetIndex);

if (targetIndex != -1) {
	console.log("数値は・・・:" + myVar[targetIndex]);
} else {
	console.log("目的の数値はみつかりませんでした・・・");
}

配列に対象の数値が含まれる場合、

C:\coding\js>node array.js
配列の大きさは:100
ターゲットは!23ですね!
targetのIndexは:21
数値は・・・:23

配列に対象の数値が含まれない場合は、こんな感じの結果になる。

C:\coding\js>node array.js
配列の大きさは:100
ターゲットは!23ですね!
targetのIndexは:21
数値は・・・:23

プログレッシブ・エンハンスメントって何?

プログレッシブ・エンハンスメントというのは、2003年に生まれた用語である。
プログレッシブ・エンハンスメントは、まず最低限の機能をベースラインとしてスタートする。
例えば、IE6とかのクソブラウザでも動くような、最低限の機能をサポートする。

で、Chromeのように、クライアントがリッチな機能をサポートしている場合のみ、機能を追加する。

アルゴリズムの勉強の参考にした本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


アルゴリズムの勉強をするならこの本、と言えるバイブル的な本。

感謝のプログラミング

今回で感謝のプログラミングは【598時間目】
10000時間まで、あと【9402時間】