Overview

This is a linear search problem where you search for a specific value in an array and find the position where it first appears.

Analysis

In this problem, you need to find a book with management number \(K\) among \(N\) books.

Key Observations

1. Finding the smallest position: Since there may be multiple books with management number \(K\), you need to answer the position where it is first found
2. Handling the non-existence case: If not found, output \(-1\)

Is a Naive Approach Sufficient?

Consider a method of checking books on the bookshelf one by one from left to right (linear search).

• In the worst case, you need to check all \(N\) books
• Since \(N \leq 2 \times 10^5\), a time complexity of \(O(N)\) is sufficient

In this problem, since the array is not sorted, faster methods like binary search cannot be used. Simply searching from the beginning in order is appropriate.

Concrete Example

For example, if \(N = 5\), \(K = 3\), \(A = [1, 3, 5, 3, 2]\): - \(A_1 = 1 \neq 3\) - \(A_2 = 3 = K\) → Found! Position is 2

The search terminates as soon as it’s first found, and the answer is \(2\).

Algorithm

1. Check elements in array \(A\) in order from the beginning
2. When you find \(i\) such that \(A_i = K\), record that position \(i + 1\) (1-indexed) and terminate the search
3. If not found until the end, output \(-1\)

result = -1
for i = 0 to N-1:
    if A[i] == K:
        result = i + 1
        break
print(result)

Complexity

• Time complexity: \(O(N)\)
  • In the worst case, each element of the array is checked once
• Space complexity: \(O(N)\)
  • Required to store the input array \(A\)

Implementation Notes

1. Converting between 1-indexed and 0-indexed: The problem counts “which position from the left” starting from 1, but program arrays start from 0, so you need to use i + 1 when outputting

2. Using the break statement: To find the smallest position, use break to exit the loop as soon as you find the first occurrence. If you forget this, the last found position will be output instead

3. Setting the initial value: By initializing with result = -1, you can concisely handle the case when the value is not found

   Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

result = -1
for i in range(N):
    if A[i] == K:
        result = i + 1
        break

print(result)

---

This editorial was generated by claude4.5opus.