【バグ発見のコツ】二分探索でバグ発生個所を特定する

あるプログラムを実行した時、その結果が想定外の値を返してきたら・・・。
あなたは、どうやってプログラムに潜んだバグを見つけ出しますか？

IDE（統合開発環境）使っている場合

ブレークポイントを張ってデバッグモードで起動する。
たいていのIDEはデバッグモードが備わっているので、１行ずつ丁寧に実行して、変数の中身を確認していけば、どこかでエラーになっている個所が見つかる（はず）。

テキストエディタで開発している場合

printデバッグする。
Javaの「System.out.println()｝や、Rubyの「print」や「puts」などを仕込んで、変数の値やロジックの通過個所などをログに出力させる。
ログファイルに出力されるような記述をすれば、本番環境での調査にも使えるので便利
・・・というか、本番調査がしやすいようなログ出力を仕込むことも大事なスキルの１つです

上記２つの方法どちらも取れない場合

二分探索する。　←今回のメインディッシュ
私は、MySQLでプロシージャを書いているときによく使います。

そもそも二分探索って？

ソート済みの配列やリストに対する検索方法の１つ。
配列の真ん中にある値と、検索したい値を大小比較し、「配列の右側にあるか、左側にあるか」を繰り返し調べていくことで、検索を行う。

どうやってプログラムのバグを見つけるの？

→プログラムの半分をコメントアウトしながら実行する。
FizzBuzz問題を例に説明します。

FizzBuzz.java

/**
 * FizzBuzz問題
 * ・１から順に数字を表示する
 * ・３で割り切れる場合：Fizz
 * ・５で割り切れる場合：Buzz
 * ・３と５で割り切れる場合：FizzBuzz
 */
public class A01_FizzBuzz {

	public static void main(String[] args) {

		int[] numArray = new int [30];
		
		for (int i = 0 ; i < numArray.length ; i++) {
			numArray[i] = i + 1;
		}
		
		for (int i = 0 ; i < numArray.length ; i++) {
			int num = numArray[i];
			if ((num % 3 == 0) && (num % 5 == 0)) {
				System.out.println("FizzBuzz");
			} else if (num % 3 == 0) {
				System.out.println("Fizz");
			} else if (num % 5 == 0) {
				System.out.println("Buzz");
			} else {
				System.out.println(num);
			}
		}
		System.out.println("finish...");
	}

}

「真ん中より右か左か？」が基本なので、まずは、プログラムの後半部分をばっさりコメントアウトします。
前半をコメントアウトすると、プログラム動かないですよね。

１回目のコメントアウト.java

public class A01_FizzBuzz {

	public static void main(String[] args) {

		int[] numArray = new int [30];
		
		for (int i = 0 ; i < numArray.length ; i++) {
			numArray[i] = i + 1;
		}
/*		
		for (int i = 0 ; i < numArray.length ; i++) {
			int num = numArray[i];
			if ((num % 3 == 0) && (num % 5 == 0)) {
				System.out.println("FizzBuzz");
			} else if (num % 3 == 0) {
				System.out.println("Fizz");
			} else if (num % 5 == 0) {
				System.out.println("Buzz");
			} else {
				System.out.println(num);
			}
		}
		System.out.println("finish...");
*/	}

}

この状態で不具合が見つかる＝プログラムの前半部分にバグがあるということなので、さらに半分をコメントアウトする・・・と繰り返していきます。

２回目のコメントアウト_前半.java

public class A01_FizzBuzz {

	public static void main(String[] args) {

		int[] numArray = new int [30];
/*		
		for (int i = 0 ; i < numArray.length ; i++) {
			numArray[i] = i + 1;
		}
		
		for (int i = 0 ; i < numArray.length ; i++) {
			int num = numArray[i];
			if ((num % 3 == 0) && (num % 5 == 0)) {
				System.out.println("FizzBuzz");
			} else if (num % 3 == 0) {
				System.out.println("Fizz");
			} else if (num % 5 == 0) {
				System.out.println("Buzz");
			} else {
				System.out.println(num);
			}
		}
		System.out.println("finish...");
*/	}

}

逆に、[１回目のコメントアウト.java]で不具合が出なければ、コメントアウトした部分に不具合が潜んでいることになります。
この場合は、コメントアウトを徐々に解除して、バグを探します。

２回目のコメントアウト_後半.java

public class A01_FizzBuzz {

	public static void main(String[] args) {

		int[] numArray = new int [30];
		
		for (int i = 0 ; i < numArray.length ; i++) {
			numArray[i] = i + 1;
		}
		
		for (int i = 0 ; i < numArray.length ; i++) {
			int num = numArray[i];
			if ((num % 3 == 0) && (num % 5 == 0)) {
				System.out.println("FizzBuzz");
			} else if (num % 3 == 0) {
				System.out.println("Fizz");
			} else if (num % 5 == 0) {
				System.out.println("Buzz");
			} else {
				System.out.println(num);
			}
		}
/*		System.out.println("finish...");
*/	}

}

アルゴリズムはプログラムだけじゃない

アルゴリズムを日本語に直すと「方法」になるかと・・・。
つまり、

• 目玉焼きのつくり方　　目玉焼きを作るためのアルゴリズム
• ○○への行き方　　○○へ行くためのアルゴリズム

という言い換えができることになる（と思ってます）。
考え方・やり方は、プログラムだけではなく、「そこに行きつくまでの方法」にも応用できますよね

余談
最後、話のまとめ方がわからなくなって迷走してる・・・
あと、例題が微妙ですね。グレーになってる部分でイメージだけつかんでいただけると幸いです。