新・アルゴリズムとデータ構造入門 Java編9:範囲に含まれる個数

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // 関数 upperBound(a, n, y) を定義

    // 変数 left, right をそれぞれ 0 と n で初期化

    // left と right が一致しない間
    // 変数 mid に (left + right) / 2 を代入

    // もし a[mid] が y より大きいなら
    // right を mid で更新
    // そうでなければ
    // left を mid + 1 で更新

    // left を返す

    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 を昇順にソート

        int q = sc.nextInt();

        int[] l = new int[q], r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();

            // upperBound(a, n, r[i]) - lowerBound(a, n, l[i]) を出力
        }
    }
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // 関数 upperBound(a, n, y) を定義

    // 変数 left, right をそれぞれ 0 と n で初期化

    // left と right が一致しない間
    // 変数 mid に (left + right) / 2 を代入

    // もし a[mid] が y より大きいなら
    // right を mid で更新
    // そうでなければ
    // left を mid + 1 で更新

    // left を返す

    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 を昇順にソート

        int q = sc.nextInt();

        int[] l = new int[q], r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();

            // upperBound(a, n, r[i]) - lowerBound(a, n, l[i]) を出力
        }
    }
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    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();
        }

        Arrays.sort(a);

        int q = sc.nextInt();

        int[] l = new int[q], r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
            System.out.println( /* ここにコードを書く */ );
        }
    }
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    static int lowerBound(int[] a, int n, int x) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    static int upperBound(int[] a, int n, int y) {

        int left = 0, right = n;

        while (left != right) {
            int mid = (left + right) / 2;

            if (a[mid] > y) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    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();
        }

        Arrays.sort(a);

        int q = sc.nextInt();

        int[] l = new int[q], r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
            System.out.println( /* ここにコードを書く */ );
        }
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「範囲外の個数」

整数 n, q と長さ n の配列 a, 長さ q の配列 l, r が与えられるので、各 l[i], r[i] について、この配列の l[i] 以下または r[i] 以上である要素の個数を出力してください。
入出力用のコードと、関数 lowerBound, upperBound がすでに用意されているので、コードを書き足してプログラムを完成させてください。

入力される値

5
5 4 3 2 1
3
1 5
2 4
3 4

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

2
4
5

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃03:範囲に含まれる個数

レベルアップ問題集「二分探索メニュー」の「ある範囲に含まれている整数の個数」の問題を解いていきます。

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編9: 二分探索 > 範囲に含まれる個数

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：