Javaの変数についておさらい。

参照

Javaでの変数は、以下の2種類
- プリミティブデータタイプ
  - int,float,double,boolean など
- オブジェクト変数(参照:reference)

new演算子、代入、引数

newは参照(オブジェクト変数)を返す。
Javaではオブジェクトは常に参照渡し。
- 新たな変数を作成しない。
- オブジェクトそのもののコピーもされない。
プリミティブデータタイプを渡す時は常に値渡し。
- 値渡しでメソッドの引数で渡される場合は、メソッドの呼び出し時に、新たな変数が作成される。
- 呼び出し側の引数の値がその新たな変数の中にコピーされる。

等値性と同一性

プリミティブとオブジェクトで、等値演算子==の効力が変わる。
- プリミティブ : 等値を検証する。
  - = 等値性
- オブジェクト : 同じオブジェクトを参照しているかを検証する。
  - = 同一性
  - オブジェクトで値を検証したいのならば、java.lang.Object#equalsを使用すること。

バイナリサーチ(二分探索)

バイナリサーチ(二分探索) ... 配列中のデータ項目数の対数に比例した実行時間を要する。

数字当てゲーム

皆さんは、1から100までの数字の中から出題者が選んだ数字を当ててくださいと言われたら、最大何回で当てられるでしょうか。

出題者はこちらの言った数字に対して、「ビンゴ」か「大きい」か「小さい」で答えてくれます。

可能性のある範囲の真ん中の数字をどんどん言ってくだけで、なんと最大7回で出題者の選んだ数字を当てることができます!!

例 : 71 1回目 : 50 ... 小さいですとの返答。残りの範囲は51 〜100になります。 2回目 : 75 ... 大きいですとの返答。残りの範囲は51 〜74になります。 3回目 : 62 ... 小さいですとの返答。残りの範囲は63 〜74になります。 4回目 : 68 ... 小さいですとの返答。残りの範囲は69 〜74になります。 5回目 : 71 ... ビンゴです。

サンプルコード

任意の値が格納されている要素を返す、探索メソッドを実装します。

public class NumTargetGame {

    public static void main(String[] args) {

        // 1〜100までの数字を用意
        // 正解をきれいにするためにindex=1 から始めます。
        int[] numArray = new int[101];
        for (int i = 1; i < numArray.length; i++) {
            numArray[i] = i;
            System.out.println(String.valueOf(numArray[i]));
        }
        find(numArray, 71);
    }

    /**
     * 二分探索
     *
     * @param numArary
     * @param answer
     * @return
     */
    private static void find(int[] numArary, int answer) {

        int lowerBound = 1;
        int upperBound = numArary.length - 1; //100
        int curIn;
        int step = 0;

        while (true) {
            step++;
            curIn = (lowerBound + upperBound) / 2;

            System.out.println("lowerBound : " + lowerBound + " upperBound : " + String.valueOf(upperBound));
            System.out.println("curIn + " + String.valueOf(curIn));

            if (numArary[curIn] == answer) {
                System.out.println(String.valueOf(step) + "回で" + String.valueOf(answer) + "を見つけられました。");
                break;
            } else if (lowerBound > upperBound) {
                System.out.println("出題者は範囲外の数字を選びました。");
                break;
            } else {
                if (numArary[curIn] < answer) {
                    lowerBound = curIn + 1;
                } else {
                    upperBound = curIn - 1;
                }
            }
        }
    }
}

ウサギとカメならカメの方になりたい

Javaの変数とバイナリサーチ(二分探索)【Javaで学ぶアルゴリズムとデータ構造】

目次