二分探索法 lower_bound と upper_bound 蟻本読書会

Contents

1 二分探索法とは？
2 lower_bound と upper_bound
3 lower_bound と upper_bound を使ってみる

二分探索法とは？

ソート済み配列に対する探索アルゴリズムの一つです。中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して検索していきます。この方法は先頭から順番に比較する方法よりも高速で目的の値を発見することができます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] A = { 0, 1, 2, 3, 4, 5 };
        int target = 0;

        int left = 0;
        int right = A.Length;

        int index = -1;
        while (true)
        {
            int mid = (left + right) / 2;
            if (target == A[mid])
            {
                index = mid;
                break;
            }
            if (right - left <= 1)
                break;

            if (target < A[mid])
                right = mid;
            else if (target > A[mid])
                left = mid;
        }
        if (index != -1)
            Console.WriteLine($"存在する index = {index}");
        else
            Console.WriteLine($"存在しない");
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int[] A = { 0, 1, 2, 3, 4, 5 };

int target = 0;

int left = 0;

int right = A.Length;

int index = -1;

while (true)

{

int mid = (left + right) / 2;

if (target == A[mid])

{

index = mid;

break;

}

if (right - left <= 1)

break;

if (target < A[mid])

right = mid;

else if (target > A[mid])

left = mid;

}

if (index != -1)

Console.WriteLine($"存在する index = {index}");

else

Console.WriteLine($"存在しない");

}

lower_bound と upper_bound

lower_bound と upper_bound は C++ のSTLライブラリにある関数で、探索したい値以上が現れる最初の位置のイテレータを取得します。インデックスを取得したい場合は、（取得したイテレータ – 探索したい領域の先頭）で取得できます。

C#で lower_bound や upper_bound と同等のメソッドを定義します。lower_boundメソッドは「指定された要素以上の値が現れる最小のインデックス」を、upper_bound では「指定された要素より大きい値が現れる最小のインデックス」を返すことにします。

lower_bound (paizaランク B 相当)

n 人の生徒が受けた、10^9 点満点のテストの採点結果 A_1, A_2, …, A_n があります。あなたは合格点を自由に設定することができます。合格点が k 点のとき、k 点以上を取った生徒が合格で、k 点未満を取った生徒が不合格です。

q 個の整数 k_1, k_2, …, k_q が与えられます。各 k_i について、合格点が k_i のときに合格する生徒の人数を答えてください。なお、n, q の最大値はいずれも 200,000 です。

入力されるデータ
n
A_1 A_2 … A_n
q
k_1
k_2
…
k_q

（ただし、1 ≦ n ≦ 200,000, 0 ≦ A_i ≦ 10^9
1 ≦ q ≦ 200,000, 0 ≦ k_i ≦ 10^9 ）

k_i が与えられるたびに、生徒ひとりひとりの点数を確認し、合格者数を求める方法では最悪で 200,000 * 200,000 回の処理が必要です。これでは実行時間制限に間に合いません。

二分探索は、このような問題にも適用することができます。A_i ≧ k を満たすような i の最小値 min がわかれば、合格者数の人数は n – min で求めることができます。lower_boundメソッドは A_i ≧ k を満たすような i の最小値 min を求めます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //lower_boundメソッドは「指定された要素以上の値が現れる最小のインデックス」
    static int lower_bound(int[] arr, int target)
    {
        if (arr[0] >= target)
            return 0;

        int left = 0;
        int right = arr.Length;

        while (right - left > 1)
        {
            int mid = (left + right) / 2;
            if (target <= arr[mid])
                right = mid;
            else if (target > arr[mid])
                left = mid;
        }
        return right;
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        A = A.OrderBy(_ => _).ToArray();

        int Q = int.Parse(Console.ReadLine());
        List<long> list = new List<long>();
        for (int i = 0; i < Q; i++)
        {
            int b = int.Parse(Console.ReadLine());
            list.Add(lower_bound(A, b));
        }

        foreach(long a in list)
            Console.WriteLine(N - a);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

//lower_boundメソッドは「指定された要素以上の値が現れる最小のインデックス」

static int lower_bound(int[] arr, int target)

{

if (arr[0] >= target)

return 0;

int left = 0;

int right = arr.Length;

while (right - left > 1)

{

int mid = (left + right) / 2;

if (target <= arr[mid])

right = mid;

else if (target > arr[mid])

left = mid;

}

return right;

}

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = A.OrderBy(_ => _).ToArray();

int Q = int.Parse(Console.ReadLine());

List<long> list = new List<long>();

for (int i = 0; i < Q; i++)

{

int b = int.Parse(Console.ReadLine());

list.Add(lower_bound(A, b));

}

foreach(long a in list)

Console.WriteLine(N - a);

}

upper_bound (paizaランク B 相当)

n 人の生徒が受けた、10^9 点満点のテストの採点結果 A_1, A_2, …, A_n があります。あなたは合格点を自由に設定することができます。合格点が k 点のとき、k 点より大きい点数を取った生徒が合格で、k 点以下の点数を取った生徒が不合格です。

q 個の整数 k_1, k_2, …, k_q が与えられます。各 k_i について、合格点が k_i のときに合格する生徒の数を答えてください。

入力されるデータと制約は前問と同じです。合格不合格の条件が変更されています。前問では「k 点以上」が合格でしたが、今回は「k 点より大きい」という条件に変更されています。upper_bound メソッドは A_i ＞ k を満たすような i の最小値 min を求めます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //upper_boundメソッドは「指定された要素より大きい値が現れる最小のインデックス」
    static int upper_bound(int[] arr, int target)
    {
        if (arr[0] > target)
            return 0;

        int left = 0;
        int right = arr.Length;

        while (right - left > 1)
        {
            int mid = (left + right) / 2;
            if (target < arr[mid])
                right = mid;
            else if (target >= arr[mid])
                left = mid;
        }
        return right;
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        A = A.OrderBy(_ => _).ToArray();

        int Q = int.Parse(Console.ReadLine());
        List<long> list = new List<long>();
        for (int i = 0; i < Q; i++)
        {
            int b = int.Parse(Console.ReadLine());
            list.Add(upper_bound(A, b));
        }

        foreach(long a in list)
            Console.WriteLine(N - a);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

//upper_boundメソッドは「指定された要素より大きい値が現れる最小のインデックス」

static int upper_bound(int[] arr, int target)

{

if (arr[0] > target)

return 0;

int left = 0;

int right = arr.Length;

while (right - left > 1)

{

int mid = (left + right) / 2;

if (target < arr[mid])

right = mid;

else if (target >= arr[mid])

left = mid;

}

return right;

}

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = A.OrderBy(_ => _).ToArray();

int Q = int.Parse(Console.ReadLine());

List<long> list = new List<long>();

for (int i = 0; i < Q; i++)

{

int b = int.Parse(Console.ReadLine());

list.Add(upper_bound(A, b));

}

foreach(long a in list)

Console.WriteLine(N - a);

}

lower_bound と upper_bound を使ってみる

Snuke Festival

祭壇の 3 カテゴリーのパーツがそれぞれ N 個ずつあります。
i 個目の上部のパーツのサイズは A_i、i 個目の中部のパーツのサイズは B_i、i 個目の下部のパーツのサイズは C_i です。

祭壇を作るにあたっては、中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより真に大きくなければなりません。

作ることのできる祭壇は何種類あるでしょうか。

N
A_1 A_2 … A_N
B_1 B_2 … B_N
C_1 C_2 … C_N

1 ≦ N ≦ 10^5
1 ≦ A_i, B_i, C_i ≦ 10^9

A, B, C それぞれを昇順ソートします。そして B[i]よりも小さいものがAのなかにどれだけあるか、B[i]よりも大きいものがCのなかにどれだけあるかを数えます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // lower_bound メソッドと upper_bound メソッドは同じなので省略

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        A = A.OrderBy(_ => _).ToArray();
        B = B.OrderBy(_ => _).ToArray();
        C = C.OrderBy(_ => _).ToArray();

        long ans = 0;
        foreach (int b in B)
        {
            // 両者の積は int の範囲内には収まりません
            long aCount = lower_bound(A, b);
            long cCount = C.Length - upper_bound(C, b);
            ans += aCount * cCount;
        }
        Console.WriteLine(ans);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// lower_bound メソッドと upper_bound メソッドは同じなので省略

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

A = A.OrderBy(_ => _).ToArray();

B = B.OrderBy(_ => _).ToArray();

C = C.OrderBy(_ => _).ToArray();

long ans = 0;

foreach (int b in B)

{

// 両者の積は int の範囲内には収まりません

long aCount = lower_bound(A, b);

long cCount = C.Length - upper_bound(C, b);

ans += aCount * cCount;

}

Console.WriteLine(ans);

}

C – ダーツ

あなたは以下のルールでダーツゲームをすることになった.

あなたは矢を的に向かって 4 本まで投げることができる。必ずしも 4 本全てを投げる必要はなく 1 本も投げなくてもかまわない。的は N 個の部分に区切られていて各々の部分に点数 P1,…, PN が書かれている。矢が刺さった場所の点数の合計 S があなたの得点の基礎となる。S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる。しかし S が M を超えた場合はあなたの得点は 0 点となる。

的に書かれている点数と M の値が与えられたとき、あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ。

入力されるデータ
N M
P1
P2
…
PN

（ただし、1 ≦ N ≦ 1000, 1 ≦ M ≦ 2 × 10^8, 1 ≦ Pi ≦ 10^8 ）

4回投げることができるので、それぞれの得点を a, b, c, d とします。a + b, c + d でペアをつくり、a + b + c + d が M を超えないような最大値になる組み合わせを探します。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // upper_bound メソッドは同じなので省略

    static void Main()
    {
        int N, M;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            M = vs[1];
        }

        List<int> A = new List<int>();
        for (int i = 0; i < N; i++)
            A.Add( int.Parse(Console.ReadLine()));
        A.Add(0); // ダーツを投げないという選択肢もあるので 0 点 を追加

        List<int> ab = new List<int>();
        for (int a = 0; a < A.Count; a++)
        {
            for (int b = 0; b < A.Count; b++)
            {
                if(A[a] + A[b] <= M) // バーストする場合は除外する
                    ab.Add(A[a] + A[b]);
            }
        }
        List<int> cd = new List<int>();
        for (int a = 0; a < A.Count; a++)
        {
            for (int b = 0; b < A.Count; b++)
            {
                if (A[a] + A[b] <= M)
                    cd.Add(A[a] + A[b]);
            }
        }

        ab = ab.Distinct().OrderBy(_ => _).ToList();
        int[] arr = cd.Distinct().OrderBy(_ => _).ToArray();

        int max = 0;
        foreach (int v in ab)
        {
            if (M - v < 0) // すでにバーストしているので除外
                continue;

            // バーストする直前の値を取得
            int index = upper_bound(arr, M - v);
            if(index - 1 >= 0) // 配列の最初の値は 0 なので 0 が返されることはないはず・・・
                max = Math.Max(max, v + arr[index - 1]);
        }
        Console.WriteLine(max);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// upper_bound メソッドは同じなので省略

static void Main()

{

int N, M;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

M = vs[1];

}

List<int> A = new List<int>();

for (int i = 0; i < N; i++)

A.Add( int.Parse(Console.ReadLine()));

A.Add(0); // ダーツを投げないという選択肢もあるので 0 点を追加

List<int> ab = new List<int>();

for (int a = 0; a < A.Count; a++)

{

for (int b = 0; b < A.Count; b++)

{

if(A[a] + A[b] <= M) // バーストする場合は除外する

ab.Add(A[a] + A[b]);

}

List<int> cd = new List<int>();

for (int a = 0; a < A.Count; a++)

{

for (int b = 0; b < A.Count; b++)

{

if (A[a] + A[b] <= M)

cd.Add(A[a] + A[b]);

}

ab = ab.Distinct().OrderBy(_ => _).ToList();

int[] arr = cd.Distinct().OrderBy(_ => _).ToArray();

int max = 0;

foreach (int v in ab)

{

if (M - v < 0) // すでにバーストしているので除外

continue;

// バーストする直前の値を取得

int index = upper_bound(arr, M - v);

if(index - 1 >= 0) // 配列の最初の値は 0 なので 0 が返されることはないはず・・・

max = Math.Max(max, v + arr[index - 1]);

}

Console.WriteLine(max);

}

C – 億マス計算

高橋君は「N^2 マス計算」で計算力をつけることにした。「N^2 マス計算」は N 行 N 列の表を用意して行う。
i 行目の左端のマスのさらに左には数 a_i が書かれており、 j 列目の上端のマスのさらに上には数 b_j が書かれている。高橋君はこの表の i 行 j 列目に a_i ×b_j の値を計算して書き込む。

すぐに解き終わってしまい退屈したので、高橋君は自分が書き込んだ N^2 個の値を昇順に並べ替えることにした。並べ替えた結果小さい方から K 番目 (1 番から数える) に位置する値を求めよ。

入力されるデータ
N K
a_1 a_2 .. a_N
b_1 b_2 .. b_N

1 ≦ N ≦ 30000
1 ≦ K ≦ N^2
1 ≦ a_i, b_i ≦ 10^9

すべてのマスに入る数を計算して K 番目の数を求めようとしても、配列に使うメモリーがとても足りそうにありません。そこでここでも二分探索法を使います。

小さい方から K 番目の値を X とすると、X とは「X 以下の数が K 個以上あるような最小の数」となります。つまり二分探索が使えるのです。

X を決めたとき、X 以下の数は何個あるかはどうやって数えればいいのでしょうか？

a * b ≦ mid なら b ≦ mid / a です。配列をソートして二分探索法を使えば a[i] に対して b[j] ≦ mid / a[i] となる配列 b 内の要素数がわかります。

upper_bound メソッドは「指定された要素より大きい値が現れる最小のインデックス」を取得するものでしたが、指定された要素以下の数を数えたいときにも使えます。前述のものは引数が int 型でしたが、ここでは long 型に変更しています。

using System;
using System.Linq;

class Program
{
    // upper_boundメソッドは「指定された要素より大きい値が現れる最小のインデックス」
    // 指定された要素以下の数を数えたいときにも使える
    static long upper_bound(long[] arr, long target)
    {
        if (arr[0] > target)
            return 0;

        long left = 0;
        long right = arr.Length;

        while (right - left > 1)
        {
            long mid = (left + right) / 2;
            if (target < arr[mid])
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    static void Main()
    {
        long N, K;
        {
            long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            N = vs[0];
            K = vs[1];
        }

        long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
        long[] B = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

        A = A.OrderBy(_ => _).ToArray();
        B = B.OrderBy(_ => _).ToArray();

        //「X以下の数がK個以上あるような最小のX」を求める
        long left = 0;
        long right = (long)Math.Pow(10, 18) + 1;

        while (right - left > 1)
        {
            long mid = (right + left) / 2;

            long k = 0;
            foreach (long a in A)
                k += upper_bound(B, mid / a);

            if (k >= K)
                right = mid;
            else
                left = mid;
        }
        Console.WriteLine(right);
    }
}

using System;

using System.Linq;

class Program

{

// upper_boundメソッドは「指定された要素より大きい値が現れる最小のインデックス」

// 指定された要素以下の数を数えたいときにも使える

static long upper_bound(long[] arr, long target)

{

if (arr[0] > target)

return 0;

long left = 0;

long right = arr.Length;

while (right - left > 1)

{

long mid = (left + right) / 2;

if (target < arr[mid])

right = mid;

else

left = mid;

}

return right;

}

static void Main()

{

long N, K;

{

long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

N = vs[0];

K = vs[1];

}

long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

long[] B = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

A = A.OrderBy(_ => _).ToArray();

B = B.OrderBy(_ => _).ToArray();

//「X以下の数がK個以上あるような最小のX」を求める

long left = 0;

long right = (long)Math.Pow(10, 18) + 1;

while (right - left > 1)

{

long mid = (right + left) / 2;

long k = 0;

foreach (long a in A)

k += upper_bound(B, mid / a);

if (k >= K)

right = mid;

else

left = mid;

}

Console.WriteLine(right);

}

二分探索法 lower_bound と upper_bound 蟻本読書会

二分探索法とは？

lower_bound と upper_bound

lower_bound と upper_bound を使ってみる

関連記事

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ