C# 二分探索法で配列のなかから最も近い値を取得する
binary-search-nearest-value
二分探索法はソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズムです。先頭からひとつずつ比較して探し出すよりも高速で必要なデータを探しだすことができるようになります。もし配列の長さが100,000の場合、先頭から調べていくと最大で100,000回の比較が必要ですが、二分探索法だと17回の比較でよくなるのです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int target = 64; int[] arr = { 49, 10, 82, 41, 64, 36, 54, 68, 29, 81 }; Array.Sort(arr); int left = 0; int right = arr.Length; bool find = false; while (right - left > 1) { int mid = (left + right) / 2; if (arr[mid] == target) { find = true; break; } if (arr[mid] < target) left = mid; if (arr[mid] > target) right = mid; } if(find) Console.WriteLine("見つかった"); else Console.WriteLine("見つからない"); } } |
二分探索法を使えば全探索をしなくても効率的に値を探すことができるようになります。
Contents
配列内にある最も近い値はどれか
配列のなかにある数と同じものはあるか？ない場合、もっとも近い数はどれかを探すときも二分探索法は使えます。
配列の要素でtargetにもっとも近いものを探すサンプルプログラムとしてよく見かけるものです。targetとの差の絶対値でもっとも小さくなるものを取得して、targetとの差の絶対値がこれと一致するものを探すという二段階作戦です。
もし配列の要素数がそんなに多くなくtargetもひとつだけというのであればこれで問題はありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Program { static void Main() { int target = 60; int[] arr = { 49, 10, 82, 41, 64, 36, 54, 68, 29, 81 }; int min = arr.Min(x => Math.Abs(x - target)); // 差の絶対値が最小になるのは 64 - 60 = 4 int ans = arr.First(x => Math.Abs(x - target) == min); // 差の絶対値が4になる要素を探す Console.WriteLine(ans); // 64と出力される } } |
ただ配列の要素数が長くてtargetが複数ある場合は二分探索法を使うと時間を短縮することができます。
これはtargetよりも大きな値と小さな値でもっとも近いものを取得するコードです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
class Program { static void Main() { int target = 64; int[] arr = { 49, 10, 82, 41, 64, 36, 54, 68, 29, 81 }; // ソートしたときに先頭と末尾に int.MinValue と int.MaxValue がつくようにする List<int> list = arr.ToList(); list.Add(int.MinValue); list.Add(int.MaxValue); arr = list.ToArray(); Array.Sort(arr); int left = 0; int right = arr.Length; while (right - left > 1) { int mid = (left + right) / 2; if (arr[mid] == target) { // 要素内にtargetが存在するときはtargetが最大値であり最小値 left = mid; right = mid; break; } if (arr[mid] < target) left = mid; if (arr[mid] > target) right = mid; } if(int.MinValue != arr[left]) Console.WriteLine($"{target}以下の値の最大値は{arr[left]}"); else Console.WriteLine($"{target}以下の値の最大値は存在しない"); if (int.MaxValue != arr[right]) Console.WriteLine($"{target}以上の値の最小値は{arr[right]}"); else Console.WriteLine($"{target}以上の値の最小値は存在しない"); } } |
応用例
これはAtCoderの競プロ典型 90 問のなかのひとつ 007 – CP Classes ですが、これは二分探索法が有効です。
ABC 競技プログラミング塾には N 個のクラスがあり、番号 i (1≦i≦N) のクラスはレーティング A[i]の生徒を対象としています。
今、Q 人の生徒がこの塾に入塾しようとしています。 番号 j (1≦j≦Q) の生徒のレーティングは B[j]です。 各生徒は自分に合わないレベルのクラスに行くと不満になります。 各生徒について、その不満度は対象レーティング a と自分のレーティング b の差の絶対値、すなわち |a-b| で定義されます。
j=1,2,3,…,Q それぞれについて生徒の不満度として考えられる最小値を求めてください。
1≦N≦300000, 1≦Q≦300000 という条件なので、長い配列のなかを何度も配列内にある最も近い値を探す処理を繰り返さないといけないので、これは二分探索法でやらないとタイムオーバーになってしまいます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] As = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int Q = int.Parse(Console.ReadLine()); int[] Bs = new int[Q]; for (int i = 0; i < Q; i++) Bs[i] = int.Parse(Console.ReadLine()); // 処理はここから List<int> list = As.ToList(); list.Add(int.MinValue); list.Add(int.MaxValue); As = list.ToArray(); Array.Sort(As); for (int i = 0; i < Q; i++) { // 二分探索法で各生徒の不満度の最小値を調べる int b = Bs[i]; int left = 0; int right = As.Length; while (right - left > 1) { int mid = (left + right) / 2; if (As[mid] == b) { left = mid; right = mid; break; } if (As[mid] < b) left = mid; if (As[mid] > b) right = mid; } int ret = Math.Min(Math.Abs(b - As[left]), Math.Abs(b - As[right])); Console.WriteLine(ret); } } } |
