概要

本棚に並ぶ \(N\) 冊の本の管理番号 \(A_i\) から、値がちょうど \(K\) である本の「最も左の位置」を見つけ、なければ \(-1\) を出力します。

考察

求めたいのは「存在するかどうか」だけでなく、「存在するなら最小の位置（左から何番目）」です。
この条件から、左から順に見ていき、初めて \(K\) を見つけた時点でそれが最小位置だと確定します。

例えば \(A = [3, 5, 2, 5],\ K=5\) のとき、左から見ていくと - 1番目: 3（違う） - 2番目: 5（一致）→ ここが最小位置なので答えは 2

このように、途中で見つかったらそれ以上探す必要がありません（早期終了できる）。

制約は \(N \le 2 \times 10^5\) なので、\(A\) を先頭から1回走査する \(O(N)\) の方法で十分間に合います。
一方で、わざわざソートして二分探索するような方法は、最小「位置」を壊してしまう（並び順が変わる）ので不適切です。また、ソートは \(O(N \log N)\) と余計です。

アルゴリズム

1. 配列 \(A\) を左から順に走査する。
2. 位置 \(i\) (1始まり) の要素 \(A_i\) が \(K\) と等しければ、その時点で \(i\) を出力して終了する。
3. 最後まで見つからなければ \(-1\) を出力する。

計算量

• 時間計算量: \(O(N)\)（最大で \(N\) 回比較するだけ）
• 空間計算量: \(O(1)\)（入力配列以外にほぼ追加領域を使わない）

実装のポイント

• 「最小の位置」を求めるので、左から順に見て最初に一致したら即終了するのが重要です。

• 出力する位置は 1始まりなので、Python では enumerate(A, 1) を使うとずれを防げます。

• 入力が大きい可能性があるため、sys.stdin.readline を使うと安定します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i, x in enumerate(A, 1):
        if x == K:
            print(i)
            return
    print(-1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。