Tìm kiếm nhị phân

Bối cảnh

Dữ liệu ban đầu chưa sắp xếp nhưng có nhiều truy vấn membership.

Hãy sort một lần rồi tự cài binary search bằng left-right-mid.

Yêu cầu

1. Sort vector tăng dần.
2. Với mỗi query x, binary search membership.
3. In YES/NO.

Yêu cầu tổ chức code

Phải có bước sort trước và binary search theo left-right-mid.

Online Judge chấm output. Với bài nhạy về cấu trúc lời giải, giảng viên có thể review source code để xác nhận học viên luyện đúng năng lực.

Input

Dòng 1 n; dòng 2 n số; dòng 3 q; q dòng x.

Output

q dòng YES/NO.

Ràng buộc

1≤n,q≤5000.

Ví dụ 1

Input

5
5 1 4 2 3
4
4
6
1
5

Output

YES
NO
YES
YES

Giải thích

Dữ liệu được sort thành 1 2 3 4 5 trước khi tìm kiếm. Với query 4, binary search thu hẹp đoạn và gặp đúng 4 nên trả YES; 6 lớn hơn mọi phần tử nên cuối cùng đoạn tìm kiếm rỗng và trả NO. Query 1 và 5 nằm ở hai đầu dãy đã sort nhưng vẫn được tìm thấy, nên lần lượt là YES, YES.

Ví dụ 2

Input

1
7
2
7
8

Output

YES
NO

Giải thích

Dãy chỉ có 7. Query 7 so sánh ngay với phần tử giữa duy nhất và thành công. Query 8 làm left vượt right sau một lần so sánh vì 7<8, nên kết luận không tồn tại. Hai dòng output là YES rồi NO.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: LAB
• Độ khó: Easy
• Concepts: binary search, left right mid, sorted precondition, membership
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100