DCT02 – Vị trí đầu tiên
Xem dạng PDF
Mã bài:
dct02
Điểm:
1 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Đề bài
Cho dãy n số nguyên đã được sắp xếp không giảm và một giá trị x. Hãy xác định vị trí đầu tiên xuất hiện x.
Chú ý: Nếu x xuất hiện nhiều lần, phải lấy vị trí nhỏ nhất. Bài toán gợi luyện việc loại bỏ một nửa khoảng tìm kiếm sau mỗi lần gọi đệ quy.
Dữ liệu vào
Dòng 1: Hai số nguyên n và x. Dòng 2: n số nguyên không giảm a1, a2, ..., an.
Dữ liệu ra
In ra vị trí xuất hiện đầu tiên của x, đánh số từ 1; nếu không tồn tại, in -1.
Ràng buộc
1 ≤ n ≤ 200000; -10^9 ≤ ai, x ≤ 10^9; a1 ≤ a2 ≤ ... ≤ an.
Ví dụ
Ví dụ 1
Input
7 2
1 2 2 2 5 8 9
Output
2
Giải thích: Giá trị 2 xuất hiện tại các vị trí 2, 3, 4; vị trí đầu tiên là 2.
Ví dụ 2
Input
5 10
1 3 5 7 9
Output
-1
Giải thích: Không có phần tử nào bằng 10.
Bình luận