Thuật toán tìm kiếm

Hai mươi câu hỏi cho một triệu cái tên

• Một cuốn điện thoại chứa một triệu cái tên. Kiểm tra từng cái một, bạn sẽ cần trung bình năm trăm nghìn phép so sánh trước khi tìm thấy cái mình muốn.
• Thay vào đó, mở ở giữa, quyết định tên nằm ở nửa nào, rồi bỏ đi nửa còn lại. Lặp lại. Bạn sẽ tìm thấy bất kỳ tên nào trong hai mươi phép so sánh.
• Năm trăm nghìn so với hai mươi không phải là sự tiết kiệm nhỏ; đó là sự khác biệt giữa một chương trình hoạt động được và một chương trình không dùng được. Và giá phải trả chỉ là một thứ: danh sách phải được sắp xếp sẵn.
• Bài học này về tìm kiếm tuyến tính và tìm kiếm nhị phân, hiệu suất của từng loại và cách lựa chọn.

Tìm kiếm tuyến tính

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1                     // not found

• Nó duyệt từ đầu đến cuối, so sánh từng phần tử với mục tiêu, và dừng lại khi tìm thấy hoặc chạm đến cuối danh sách.
• Nó hoạt động trên bất kỳ danh sách nào, đã sắp xếp hay chưa, và trên mọi cấu trúc dữ liệu có thể duyệt qua từng bước.
• Trường hợp xấu nhất: mục tiêu nằm ở cuối hoặc không tồn tại, nên tất cả $n$ phần tử đều được so sánh, tức là $O(n)$. Trung bình thì khoảng một nửa.

Kiểm tra từng cái một, bắt đầu từ đầu

Tìm kiếm nhị phân

low ← 1 ;  high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE high ← mid - 1
ENDWHILE
RETURN -1

• Nó yêu cầu dữ liệu phải được sắp xếp. So sánh phần tử ở giữa với mục tiêu: nếu khớp thì dừng; nếu mục tiêu lớn hơn thì loại bỏ nửa dưới; ngược lại thì loại bỏ nửa trên.
• Mỗi phép so sánh cắt đôi phạm vi cần tìm, nên số phép so sánh là $O(\log_2 n)$.
• Đó là lý do một triệu phần tử cần khoảng hai mươi phép so sánh: $2^{20}$ lớn hơn một chút so với một triệu.

Ví dụ giải chi tiết: truy vết tìm kiếm nhị phân

Chọn giữa hai loại

• Sắp xếp ban đầu tốn kém hơn một lần tìm kiếm tuyến tính, nên tìm kiếm nhị phân chỉ có lợi thế khi danh sách đã sắp xếp sẵn hoặc sẽ được tìm kiếm rất nhiều lần.
• Tìm kiếm nhị phân cũng cần truy cập trực tiếp đến phần tử ở giữa, điều mà mảng có nhưng danh sách liên kết không có.

Ví dụ minh họa: lập luận cho lựa chọn

Chi phí duy trì file đã sắp xếp

• Tìm kiếm nhị phân chỉ khả dụng trên danh sách đã sắp xếp, và việc sắp xếp đó không miễn phí. Một câu hỏi yêu cầu bạn justifying (giải thích) một lựa chọn đang yêu cầu bạn định giá chi phí đó.
• Nếu dữ liệu được tìm kiếm thường xuyên và thay đổi hiếm, hãy sắp xếp nó một lần và mọi lần tìm kiếm sau sẽ là $\log_2 n$. Đó là trường hợp của từ điển hoặc bảng tra cứu.
• Nếu dữ liệu thay đổi liên tục, mỗi lần chèn đều phải giữ nguyên thứ tự, điều này tốn chi phí di chuyển các phần tử phía sau. Khi đó, tìm kiếm tuyến tính trên dữ liệu không sắp xếp có thể có tổng chi phí thấp hơn.
• Các con số giúp lập luận cụ thể: một triệu bản ghi cần tối đa một triệu lần so sánh theo phương pháp tuyến tính, nhưng chỉ 20 theo tìm kiếm nhị phân, bởi vì $2^{20} > 10^6$.
• Vì vậy, câu trả lời được chấm điểm cần nêu cả hai yếu tố: tần suất tìm kiếm và tần suất thay đổi.

Điểm số dễ mất

Bạn đã nắm vững