Tìm kiếm nhị phân đệ quy

Binary-search Buổi 05 — Hàm & Đệ quy
Points
34
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho một dãy số nguyên tăng dần nghiêm ngặt $A_1 < A_2 < \dots < A_N$ và $Q$ truy vấn. Với mỗi truy vấn là một số nguyên $X$, hãy viết hàm tìm kiếm nhị phân đệ quy để trả về vị trí của $X$ (đánh số từ 1) trong dãy $A$, hoặc -1 nếu không tìm thấy.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $Q$. Dòng thứ hai chứa $N$ số nguyên của dãy $A$. $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $X$.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Ví dụ
Input Output
5 3\n2 5 8 12 16\n8\n3\n16 3\n-1\n5
1 2\n10\n10\n5 1\n-1
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |X| \le 10^9$.

Draft saved