🎯

【Java】二分探索2

2024/05/07に公開

Java

初心者

tech

例題

サイズnの配列aの要素の中には、サイズqの配列kの各要素k[i]以上の個数は何個あるか求めよ。

例題の値

n = 10
a = 10 9 8 7 6 5 4 3 2 1
q = 2
k = 5 7

例題の答え

k[0] = 5の場合の答えは、下記の6個。

5 6 7 8 9 10

k[1] = 7の場合の答えは、下記の4個。

7 8 9 10

アルゴリズム

考え方
- 配列aを昇順にソート
- x未満とx以上の境界を探し、x以上の要素数を求める
- 境界の探すために二分探索を使用
二分探索による境界の探し方
ソートされた配列aと境界の関係性は、下記の通り
```
| a[0] | a[1] |  …  |  a[n - 2] | a[n - 1] |
0      1      2    n-2         n-1         n
```
- 境界の左端l = 0、境界の右端r = nとして、二分探索を開始
- l == rになるまで境界の位置を二分探索 → l != rの間は探索を続ける
- 中央の境界をmid = (l + r) / 2（切り捨て）とする
- 境界の位置はmidより右なのか左なのかを判定
二分探索の条件判定
- a[mid] >= x なら境界はその位置かそれより左
  - r = mid でrを更新
- a[mid] < x なら境界はそれより右
  - l = mid + 1 でlを更新
境界の位置と答えについて
- x未満とx以上の境界の位置はl（またはr、なぜなら境界の位置はl == rだから）
- x以上の要素数はn - l

コード例

import java.util.*;

public class Main {

    // メソッド binarySearch(a, n, x) を定義
    static int binarySearch(int[] a, int n, int x) {
        // 変数 l = 0, r = n で初期化
        int l = 0, r = n;
        
        // l と r が一致しない間
        while (l != r) {
            // 中央の要素 mid に (l + r) / 2 を代入
            int mid = (l + r) / 2;
            
            // もし a[mid] が x 以上なら
            if (a[mid] >= x) {
                // r を mid で更新
                r = mid;
            // そうでなければ
            } else {
                // left を mid + 1 で更新
                l = mid + 1;
            }
        }
        // l を返す
        return l;
    }
    

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

        int n = sc.nextInt();

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

        // 配列 a を昇順にソート
        Arrays.sort(a);

        int q = sc.nextInt();

        int[] k = new int[q];
        for (int i = 0; i < q; i++) {
            k[i] = sc.nextInt();
            // binarySearchメソッドを呼び出して、n - l を出力
            System.out.println(n - binarySearch(a, n, k[i]));
        }
    }
}

例題

例題の値

例題の答え

アルゴリズム

コード例

Discussion