Tìm kiếm: linear, binary và interpolation

Giới thiệu

Bài này học 3 cách tìm kiếm nhanh dần. Bạn chọn đúng cách theo dữ liệu.

Kiến thức cần nhớ

Linear — quét cạn

• Duyệt từng món tới khi trúng hoặc hết.
• Không cần sắp xếp trước.
• Chậm $O(n)$ khi kho to.
• Ví dụ đời thường: tìm chìa khóa khắp nhà.
• Hợp dữ liệu nhỏ hoặc tìm 1-2 lần.

Binary — chặt đôi

• Cần dữ liệu đã sắp xếp trước.
• Mỗi lượt loại nửa vùng tìm kiếm.
• Tốn $O(log n)$ bước.
• Ví dụ đời thường: đoán số từ 1 tới 100.
• Hợp kho đã xếp hoặc tìm lặp nhiều lần.

Interpolation — đoán vị trí

• Cũng cần dữ liệu đã sắp xếp.
• Dùng giá trị để đoán vị trí, không chém giữa mù.
• Dữ liệu phân bố đều thì trung bình $O(\log \log n)$, lệch nặng thì tệ nhất $O(n)$.
• Ví dụ đời thường: mở từ điển ngay quãng chữ R.

Ví dụ

• Input: 12,33,11,99,22, tìm 12 kiểu quét. Output: trúng ngay lần đầu.
• Giải thích: quét từ đầu nên món đầu tiên trúng luôn.

# Quét tuyến tính
for i, x in enumerate(a):  # duyệt từng món
    if x == target:  # trúng thì dừng
        print(i)
        break

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-013/. Mọi hàm trả chỉ số tìm thấy, không thấy trả -1, và đếm số lần so sánh qua tham số long long &cmp.

Bài 1: Linear và binary search

linear [12,33,11,99,22], 12      -> 0, cmp=1
linear [12,33,11,99,22], 7       -> -1, cmp=5
binary [1,3,5,7,9,11], 7         -> 3
binary [1,3,5,7,9,11], 4         -> -1
lowerBound [1,2,2,2,5], 2        -> 1
upperBound [1,2,2,2,5], 2        -> 4   (số lần xuất hiện của 2 = 4 - 1 = 3)
mảng rỗng                        -> -1 / 0

Bài 2: Interpolation search

Viết int interpolationSearch(const std::vector<int>&, int x, long long &cmp). Chặn chia cho 0 khi a[lo] == a[hi].

Sinh 2 mảng cỡ $10^6$:

• Đều: a[i] = 3 * i.
• Lệch: a[i] = i * i.

Tìm 1000 giá trị ngẫu nhiên có trong mảng. In số so sánh trung bình:

data      binary_avg_cmp   interp_avg_cmp
uniform   ~20              ~2-3
skewed    ~20              ...

Bài 3: Tìm kiếm trên đáp án (nâng cao)

Dùng binary search trên khoảng giá trị, không phải trên mảng:

1. long long isqrt(long long n): số nguyên lớn nhất r có r*r <= n. Test isqrt(0)=0, isqrt(15)=3, isqrt(16)=4, isqrt(10^18)=10^9.
2. Có n gói hàng khối lượng w[i], chở trong đúng thứ tự bằng d ngày. Tìm tải trọng xe nhỏ nhất. w=[1..10], d=5 -> 15.
3. Mảng tăng dần bị xoay (ví dụ [4,5,6,7,0,1,2]). Tìm x trong $O(\log n)$. Tìm 0 -> chỉ số 4.

✅ Tiêu chí hoàn thành

• Test mẫu pass. Có test ngẫu nhiên so binarySearch với std::binary_search.
• lowerBound/upperBound đúng khi mọi phần tử bằng nhau hoặc x ngoài khoảng.
• Bảng Bài 2 có số thật.
• Giải thích được: xếp 1 lần tốn $O(n \log n)$, sau bao nhiêu lần tìm thì đáng hơn quét tuyến tính.

❓ Câu hỏi ôn tập

• Quét cạn cần xếp trước không?
• Chặt đôi cần điều kiện gì?
• Nội suy thắng khi dữ liệu thế nào?
• Tìm 1 lần trên kho chưa xếp thì dùng gì?

🌕 Bạn đã hoàn thành ngày 13. Làm hết bài tập phía trên rồi sang ngày tiếp theo.