Tìm kiếm nhị phân trên dãy đã sắp xếp
Dãy đã được sắp xếp tăng dần, nên ta không cần quét từng phần tử. Mỗi lần so sánh với phần
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Dãy đã được sắp xếp tăng dần, nên ta không cần quét từng phần tử. Mỗi lần so sánh với phần tử giữa dãy ta loại được một nửa số ứng viên, và đó là ý tưởng của tìm kiếm nhị phân.
Yêu cầu
Cho một dãy n số nguyên tăng dần nghiêm ngặt (a1 < a2 < ... < an) và một giá trị x. Hãy in ra vị trí (đếm từ 1) của x trong dãy, hoặc -1 nếu x không có trong dãy. Vì các phần tử đôi một khác nhau nên vị trí cần tìm là duy nhất.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin đúng định dạng trên, in ra stdout một số nguyên duy nhất là vị trí đếm từ 1 hoặc -1.
Input
- Dòng 1: hai số nguyên n và x (1 <= n <= 30, -10000 <= x <= 10000).
- Dòng 2: n số nguyên tăng dần nghiêm ngặt (-10000 <= ai <= 10000).
Output
Một số nguyên: vị trí của x tính từ 1, hoặc -1 nếu không tìm thấy.
Ràng buộc
- Dãy đã sắp xếp tăng dần và không có hai phần tử bằng nhau.
- Có thể giải bằng quét tuyến tính, nhưng hãy luyện đúng kỹ thuật chia đôi khoảng tìm.
- Mỗi bộ dữ liệu chạy trong 1 giây.
Ví dụ 1
Input
5 7
1 3 5 7 9
Output
4
Ví dụ 2
Input
6 1
1 2 3 4 5 6
Output
1
Giải thích
Dữ liệu vào:
Phần tử 7 nằm ở vị trí thứ 4, nên in ra 4.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
