🎯

【Java】二分探索

2024/05/01に公開

Java

初心者

tech

二分探索とは

二分探索とは、ソートされた配列やリストから特定の要素を効率的に探すアルゴリズムの一種です。配列やリストがソートされていることが前提となります。具体的には、下記の通り探したい要素を探索します。

ソートされた配列やリストの中央にある要素(mid)を調べます。
探している要素(x)と中央の要素(mid)を比較します。
探している要素(x)が中央の要素(mid)と等しい場合、探索は終了です。
探している要素(x)が中央の要素(mid)より大きい場合、中央より右側の部分配列や部分リストを対象として探索を行います。
探している要素(x)が中央の要素(mid)より小さい場合、中央より左側の部分配列や部分リストを対象として探索を行います。

例題

サイズnの昇順にソートされた配列aに探したい要素xが含まれているか求めよ。

アルゴリズム

探索対象は配列全体a[0] ～ a[n - 1]
左端l=0とし、右端r=n-1とすると、a[l]～a[r]を探索
中央の要素をmid=(l + r) / 2（切り捨て）とし、
a[mid] == xなら、探索終了
a[mid] > xなら、midより左側を探索
- r=mid-1とし、rを更新して、l～mid-1を探索
a[mid] < xなら、midより右側を探索します
- l=mid+1とし、lを更新して、mid+1～rを探索

コード例

import java.util.*;

public class Main {

    static boolean binarySearch(int n, int x, int[] a) {

        // 変数 l, r をそれぞれ 0 と n - 1 で初期化
        int l = 0, r = n - 1;
        // r が l 以上である間
        while (l <= r) {
            // 変数 mid に (l + r) / 2 を代入
            int mid = (l + r) / 2;
            // もし a[mid] が x に等しいなら
            if (a[mid] == x) {
                // true を返す
                return true;
            // もし a[mid] が x より大きいなら
            } else if (a[mid] > x) {
                // r に mid - 1 を代入
                r = mid - 1;
            // そうでなければ
            } else {
                // l に mid + 1 を代入
                l = mid + 1;
            }
        }
        // false を返す
        return false;
    }

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

        int n = sc.nextInt(), x = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        System.out.println(binarySearch(n, x, a) ? "Yes" : "No");
    }
}

入力値1

3 1
1 4 9

出力結果1

Yes

入力値2

3 2
1 4 9

出力結果2

No

二分探索とは

例題

アルゴリズム

コード例

Discussion