Cho một dãy số nguyên A gồm N phần tử đã được sắp xếp theo thứ tự tăng dần. Có Q truy vấn, mỗi truy vấn gồm một số nguyên X. Hãy kiểm tra xem X có xuất hiện trong dãy A hay không.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và Q.

Dòng 2: N số nguyên là các phần tử của dãy A.

Q dòng tiếp theo: Mỗi dòng chứa một số nguyên X cần tìm.

Dữ liệu ra:

Với mỗi truy vấn, in ra "YES" nếu X xuất hiện trong A, ngược lại in ra "NO".

Ràng buộc:

1 <= N, Q <= 10^5

A[i]|, |X| <= 10^9

Ví dụ:

Input:

5 3 
1 3 5 7 9 
3 
4
9

Output:

YES 
NO 
YES

Cho một dãy số nguyên A gồm N phần tử đã được sắp xếp theo thứ tự tăng dần. Hãy kiểm tra xem số nguyên X có xuất hiện trong dãy hay không.

Dữ liệu vào:

Dòng đầu tiên chứa hai số nguyên dương N và X.

Dòng thứ hai chứa N số nguyên A[1], A[2], ..., A[N], các số cách nhau bởi dấu cách.

Dữ liệu ra:

In ra "YES" nếu X xuất hiện trong dãy, ngược lại in ra "NO".

Giới hạn:

1 <= N <= 10^5

|A[i]|, |X| <= 10^9

Ví dụ:

Input:

5 3
1 2 3 4 5

Output:

YES

Cho dãy số A gồm N số nguyên đã sắp xếp tăng dần. Hãy tìm chỉ số (vị trí) của số X trong dãy. Nếu X không tồn tại, in ra -1. Quy ước chỉ số bắt đầu từ 1.

Dữ liệu vào:

Dòng 1: N và X.

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Một số nguyên duy nhất là vị trí của X hoặc -1.

Giới hạn:

1 <= N <= 10^5

Các phần tử trong mảng đôi một khác nhau.

Ví dụ:

Input:

5 4
1 3 4 7 9

Output:

3

Cho dãy số A gồm N phần tử được sắp xếp theo thứ tự GIẢM dần. Hãy kiểm tra xem X có tồn tại trong dãy không.

Dữ liệu vào:

Dòng 1: N và X.

Dòng 2: N số nguyên A[i] (A[1] >= A[2] >= ... >= A[N]).

Dữ liệu ra:

In ra "YES" hoặc "NO".

Giới hạn:

1 <= N <= 10^5

Ví dụ:

Input:

5 2
5 4 3 2 1

Output:

YES

Cho một mảng A nguyên gồm N phần tử đã sắp xếp tăng dần, hãy tìm chỉ số của phần tử x xuất hiện đầu tiên trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số x = 5 thì số 5 xuất hiện đầu tiên sẽ có chỉ số 3, in ra chỉ số này. Nếu không tìm thấy in ra -1.

Ràng buộc: ~0 < N \leq 10^6~, ~-10^6 < A[i] \leq 10^6~

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

3

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

0

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho một mảng A nguyên gồm N phần tử, hãy tìm chỉ số của phần tử xuất hiện cuối cùng trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số 5 thì số 5 xuất hiện cuối cùng sẽ có chỉ số 5, chỉ số này được in ra. Nếu không tìm thấy thì in ra -1

Ràng buộc: ~0 < N \leq 10^6~, ~-10^6 < A[i] \leq 10^6~

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

5

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

1

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho mảng A gồm N phần tử. Sử dụng hàm có sẵn tìm vị trí đầu tiên của phần tử lớn hơn hoặc bằng X.

Dòng đầu tiên nhập N và X

Dòng tiếp theo nhập N giá trị của mảng A

In ra vị trí nếu tìm thấy, nếu không tìm thấy thì in ra N.

Ràng buộc: ~0 < N \leq 10^6~; ~0 \leq A[i] \leq 10^9~

Input 01:

10 6
3 5 6 6 6 6 9 10 11 13

Output 01:

2

Vị trí đầu tiên trong mảng lớn hơn hoặc bằng 6 là vị trí có chỉ số là 2 (có giá trị là 6)

Input 02:

10 14
3 5 6 6 6 6 9 10 11 13

Output 02:

10

Cho mảng A gồm n phần tử. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất (phải thuộc mảng A) lớn hơn Ai (i = 0, 1, 2,, n-1). Đưa ra ký tự _ nếu Ai không có phần từ lớn hơn nó. Ví dụ với mảng A = (13, 6, 7, 12) ta có kết quả là (_ , 7, 12, 13).

Định dạng đầu vào: Dòng đầu tiên đưa vào n là số phần tử của mảng A; Dòng kế tiếp đưa vào n số A[i] của mảng; các số được viết cách nhau một vài khoảng trống.

Ràng buộc: 1 <= N <= 10^5; 1 ≤ A[i] <= 10^5.

Định dạng đầu ra: Đưa ra kết quả trên 1 dòng

Input:

9
6 3 9 8 10 2 1 15 7

Output:

7 6 10 9 15 3 2 _ 8

Cho một mảng A các số nguyên có N phần tử, sử dụng hàm tìm kiếm nhị phân có sẵn để tìm kiếm giá trị X nhập từ bàn phím

Dòng đầu tiên nhập N và X

Dòng tiếp theo nhập N giá trị của mảng A

In ra FOUND nếu tìm thấy và NOT FOUND nếu không tìm thấy

Ràng buộc: ~0 < N \leq 10^6~; ~0 \leq A[i] \leq 10^9~

Input:

5 6
3 5 6 9 13

Output:

FOUND

Cho một mảng A gồm N số nguyên chưa được sắp xếp. Có Q truy vấn được đưa ra, mỗi truy vấn yêu cầu bạn kiểm tra một số nguyên X và đếm xem X xuất hiện bao nhiêu lần trong mảng A.

Gợi ý: Vì số lượng truy vấn Q rất lớn, việc dùng vòng lặp quét toàn bộ mảng cho mỗi câu hỏi sẽ bị quá thời gian. Các em cần sắp xếp mảng trước, sau đó vận dụng Tìm kiếm nhị phân (hoặc các hàm lowerbound, upperbound trong C++) để tối ưu hóa thời gian tìm kiếm.

Đầu vào:

• Dòng thứ nhất chứa hai số nguyên dương N và Q lần lượt là số lượng phần tử của mảng và số lượng truy vấn.

• Dòng thứ hai chứa N số nguyên A[i] cách nhau bởi khoảng trắng.

• Q dòng tiếp theo, mỗi dòng chứa một số nguyên X tương ứng với một truy vấn.

Ràng buộc:

• 1 <= N, Q <= 10^5

• -10^9 <= A[i], X <= 10^9

Đầu ra:

In ra Q dòng, mỗi dòng là số lần xuất hiện của X tương ứng với từng truy vấn.

Ví dụ:

Input 01:

5 3
5 1 4 6 3
3
6
10

Output 01:

1
1
0

Input 02:

6 4
1 3 1 4 1 7
1
2
4
7

Output 02:

3
0
1
1