Truy Vấn Cận Dưới (Lower Bound Binary Search)

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm Buổi 10 — STL Algorithms sorting
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho mảng A gồm N số nguyên đã được sắp xếp tăng dần (chỉ số từ 1 đến N) và Q truy vấn. Với mỗi truy vấn gồm số nguyên X, hãy tìm chỉ số i nhỏ nhất (1 ≤ i ≤ N) sao cho A[i] ≥ X. Nếu không tồn tại phần tử nào ≥ X, in ra -1.

Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên dương N và Q (1 ≤ N, Q ≤ 10^5).
  • Dòng 2: N số nguyên A[1] ≤ A[2] ≤ ... ≤ A[N].
  • Dòng 3: Q số nguyên X cần truy vấn.
Dữ liệu ra (Output)
  • Gồm Q dòng, mỗi dòng in ra chỉ số đầu tiên tìm được (1-indexed) hoặc -1.
Ví dụ mẫu
Sample Input 1
5 3
2 4 4 7 9
4 8 10
Sample Output 1
2
5
-1
Draft saved