Số Nguyên Ẩn

Hướng tiếp cận

Bài toán yêu cầu tìm một số trong đoạn $[1,{10}^9]$ với tối đa $30$ câu hỏi dạng "số $y$ có nhỏ hơn $x$ không?". Đây là bài toán tìm kiếm nhị phân cổ điển.

Nhận xét quan trọng

1. Mỗi câu hỏi chia đôi không gian tìm kiếm: nếu $y<x$ thì $x\in [y+1,hi]$, ngược lại $x\in [lo,y]$.
2. Với $30$ câu hỏi, ta có thể tìm trong đoạn có kích thước tối đa $2^{30}=1,073,741,824>{10}^9$.

Thuật toán

1. Khởi tạo $lo=1$, $hi={10}^9$.
2. Trong khi $lo<hi$:
   • Tính $mid=\lfloor (lo+hi)/2\rfloor$.
   • Hỏi ? mid.
   • Nếu câu trả lời là YES ($mid<x$): gán $lo=mid+1$.
   • Nếu câu trả lời là NO ($mid\ge x$): gán $hi=mid$.
3. Khai báo ! lo.

Độ phức tạp

• Số câu hỏi: $O({\log }_2{10}^9)=30$
• Thời gian: $O(\log n)$
• Bộ nhớ: $O(1)$