はじめに

自分用の備忘録

問題文

下記のリンクを参考にしてください。

解答例

import java.util.Scanner;

public class Main {
    static int N, X;
    static int[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        X = sc.nextInt();

        A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = sc.nextInt();
        }

        int answer = search(X);
        System.out.println(answer);

    }

    static int search(int givienValue) {
        int answer = -1;
        int L = 1, R = N;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] > givienValue) {
                R = M - 1;
            }

            if (A[M] == givienValue) {
                return M;
            }

            if (A[M] < givienValue) {
                L = M + 1;
            }
        }
        return answer;
    }
}

所感と解説

まだバイナリサーチのイメージがつかめていない気がする。だから、誰かに説明したり、ブログでまとめたりして、まずはイメージを作る。こからサクサクとコードをかけるようにしたい！

このコードは、バイナリサーチ（二分探索）を実装したものです。バイナリサーチは、ソート済みの配列に対して特定の値を効率的に探すためのアルゴリズムです。

以下に、各部分の詳細な説明を提供します。

import java.util.Scanner;

public class Main {
    static int N, X;
    static int[] A;

この部分では、必要なライブラリをインポートし、使用する変数を宣言しています。NとXは整数型の変数で、Aは整数型の配列です。

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        X = sc.nextInt();

        A = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = sc.nextInt();
        }

        int answer = search(X);
        System.out.println(answer);
    }

main関数では、まずScannerオブジェクトを作成して、標準入力から値を読み取ります。次に、NとXの値を読み取り、N+1の長さの配列Aを作成します。その後、配列Aの各要素に値を読み込みます。最後に、search関数を呼び出してXの位置を探し、その結果を出力します。

    static int search(int givienValue) {
        int answer = -1;
        int L = 1, R = N;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] > givienValue) {
                R = M - 1;
            }

            if (A[M] == givienValue) {
                return M;
            }

            if (A[M] < givienValue) {
                L = M + 1;
            }
        }
        return answer;
    }
}

search関数は、バイナリサーチの実装部分です。この関数は、配列Aの中でgivienValueと等しい値を探し、その位置（インデックス）を返します。LとRは探索範囲の左端と右端を表します。探索範囲が存在する（L <= R）限り、中央の位置Mの値を確認します。A[M]がgivienValueより大きい場合、探索範囲を左半分（LからM-1）に更新します。A[M]がgivienValueと等しい場合、その位置Mを返します。A[M]がgivienValueより小さい場合、探索範囲を右半分（M+1からR）に更新します。探索範囲が存在しなくなったら（L > R）、givienValueは配列Aに存在しないと判断し、-1を返します。

以上が、このコードの詳細な説明です。このコードは、バイナリサーチを用いて特定の値を効率的に探すためのもので、競技プログラミングなどでよく使われるテクニックです。このコードを理解することで、バイナリサーチの基本的な考え方と実装方法を学ぶことができます。

失敗記録

2024/03/17

復習の時に、、int M = (L + R) / 2;をwhileの外に書いてしまった。くやしい。でも、これが自然と出来るようになればレベルアップだぜ！

2024/03/20

どの値を比べるのかを意識していこう！今回の問題だと、配列の中身とXを比べる必要があるよね！

Before

if (Mid < Y) {
                left = Mid + 1;
            }

After

if (A[Mid] < Y) {
                left = Mid + 1;
            }

参考文献

github.com

taiPyのお悩み解決ブログ

日々の発見をまとめます！

Javaの解答例：A11 - Binary Search 1, H競技プログラミングの鉄則