二分探索（AtCoder:ABC077）

Question

前提

AtcoderのABC077の問題(https://abc077.contest.atcoder.jp/tasks/arc084_a
)を二分探索を使って解いたのですが、
なぜ間違っているのかわかりませんでした。

問題の詳細は上記のAtCoderのリンク先のページを参照いただきたいのですが、
ざっくりというと、入力の配列とKEY値に対して、KEY値よりも大きい数の要素の個数とKEY値よりも小さい数の要素の個数を求める問題です。

質問内容

質問させていただきたいことは、下記のbinarySearchメソッドで、KEY値と入力の配列の要素の数が一致した場合に、

「return midでmid値をreturnするとNGで、
mid = rightにして、最終的にreturn rightでright値をreturnするとOK」となります。
が、なぜそうなるのかわからず・・・。どちらも同じように見えてしまうのです。
return midでmid値をreturnするとNG の理由を教えていただけないでしょうか。

よろしくお願いいたしますm(_ _)m

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

public class Main {

	public static void main2(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		// b[i]がKEY値の配列
		for (int i = 0; i < n; i++) {
			b[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
		}
		Arrays.sort(a);
		Arrays.sort(c);

		long ans = 0;
		for (int i = 0; i < n; i++) {
			ans += binarySearch(b[i], a) * (n - binarySearch(b[i] + 1, c));
		}
		System.out.println(ans);
	}

	private static long binarySearch(int key, int[] a) {

		int left = 0;
		int right = a.length;
		int mid;

		while (left < right) {
			mid = (left + right) / 2;
			if (key == a[mid]) {
				/*
				 * ここで、retun mid にするとNGで、right = mid にするとOKなのですが
				 * その理由が分かりませんでした。
				 * どちらも同じように思えてしまうのです。
				 */
				return mid;
//				right = mid;
			} else if (key < a[mid]) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}
}

Answer 1

たとえば a[] = { 1, 2, 2, 2, 2, 2, 3 } に対して 2 を検索したとき、
いきなり mid 返しちゃイカンと思うぞ?
※ 最初に見つかった(左端の)2の位置を返さんと。

Comments

[d_tutuz]

配列にて数が重複することを失念しておりました。
理解できました。ありがとうございます！

Answer 2

きっと３つか４つぐらいの小さな配列を用いて自分で結果に対して計算してみるとなぜかがわかると思います。a,b,cを全て

{1,2,3}

だと仮定してi=1のときの計算をしてみたらどういうことになるでしょう？

論理を考えるときに「まず境界条件について正しいか」を確認し、「それに基づき一般解として正しいか」を検証のは有効でよく用いる手段であると思います。