TKNP: Một số bài làm quen với tìm kiếm nhị phân
Bài
| # | Bài | Điểm | Lời giải |
|---|---|---|---|
| 1 | TKNP01: Thấy hay không thấy | 200 | |
| 2 | TKNP02: Tìm X | 200 | |
| 3 | TKNP03: Đếm số | 200 | |
| 4 | TKNP04: Đếm số trong đoạn | 200 | |
| 5 | TKNP05: Đoạn chỉ số | 200 | |
| 6 | [Beginner Free Contest 13] RBPOINT2 | 400 | |
| 7 | [TKNP] ESEQ | 400 | |
| 8 | [TKNP] MAXVAL | 400 | |
| 9 | [TKNP] SQUIRR2 | 400 | |
| 10 | [TKNP] FGIFT | 400 | |
| 11 | [TKNP] MINK | 400 | |
| 12 | Khách hàng may mắn (Đề HSG 9 Phú Thọ 2022-2023) | 400 | Lời giải |
| 13 | Cắt dây điện | 400 | |
| 14 | Thi đấu cầu lông (KS THCS 05) | 500 | |
| 15 | Phát quà (KS3) | 500 |
Tìm kiếm nhị phân là kĩ thuật tìm kiếm dựa trên dãy đã sắp xếp, có thời gian tìm kiếm trung bình O(logN) trên dãy N phần tử, rất nhanh so với O(N) của tìm kiếm tuần tự. Giải thích: log(N) hay log2(N) là 1 số nguyên dương x sao cho 2^x = N. Ví dụ nếu N = 128 -> log(N) = 8 N = 4294967296 -> log(N) = 32 (tức là chỉ cần kiểm tra 32 số để tìm một số trong dãy hơn 4 tỉ số)
Bình luận