Giải thuật Tìm kiếm nội suy (Interpolation Search)
Giải thuật Tìm kiếm nội suy (Interpolation Search) là gì?
Tìm kiếm nội suy (Interpolation Search) là biến thể cải tiến của Tìm kiếm nhị phân (Binary Search). Để giải thuật tìm kiếm này làm việc chính xác thì tập dữ liệu phải được sắp xếp.
Binary Search có lợi thế lớn về độ phức tạp thời gian khi so sánh với Linear Search. Linear Search có độ phức tạp trường hợp xấu nhất là Ο(n) trong khi Binary Search là Ο(log n).
Có một số tình huống mà vị trí của dữ liệu cần tìm có thể đã được biết trước. Ví dụ, trong trường hợp danh bạ điện thoại, nếu chúng ta muốn tìm số điện thoại của Hương chẳng hạn. Trong trường hợp này, Linear Search và cả Binary Search có thể là chậm khi thực hiện tìm kiếm, khi mà chúng ta có thể trực tiếp nhảy tới phần không gian bộ nhớ có tên bắt đầu với H được lưu giữ.
Xác định vị trí trong Binary Search
Trong Binary Search, nếu dữ liệu cần tìm không được tìm thấy thì phần còn lại của danh sách được phân chia thành hai phần: phần bên trái (chứa giá trị nhỏ hơn) và phần bên phải (chứa giá trị lớn hơn). Sau đó tiến trình tìm kiếm được thực hiện trên một trong hai phần này.
Dò vị trí trong Tìm kiếm nội suy (Interpolation Search)
Tìm kiếm nội suy tìm kiếm một phần tử cụ thể bằng việc tính toán vị trí dò (Probe Position). Ban đầu thì vị trí dò là vị trí của phần tử nằm ở giữa nhất của tập dữ liệu.
Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Để chia danh sách thành hai phần, chúng ta sử dụng phương thức sau:
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) Trong đó: A = danh sách Lo = chỉ mục thấp nhất của danh sách Hi = chỉ mục cao nhất của danh sách A[n] = giá trị được lưu giữ tại chỉ mục n trong danh sách
Nếu phần tử cần tìm có giá trị lớn hơn phần tử ở giữa thì phần tử cần tìm sẽ ở mảng con bên phải phần tử ở giữa và chúng ta lại tiếp tục tính vị trí dò; nếu không phần tử cần tìm sẽ ở mảng con bên trái phần tử ở giữa. Tiến trình này tiến tụp diễn ra trên các mảng con cho tới khi kích cỡ của mảng con giảm về 0.
Độ phức tạp thời gian chạy của Interpolation Search là Ο(log (log n)), trong khi của Binary Search là Ο(log n).
Giải thuật Tìm kiếm nội suy
Bởi vì đây là sự cải tiến của giải thuật Binary Search nên chúng ta sẽ chỉ đề cập tới các bước để tìm kiếm chỉ mục của giá trị cần tìm bởi sử dụng vị trí dò.
Bước 1 : Bắt đầu tìm kiếm dữ liệu từ phần giữa của danh sách Bước 2 : Nếu đây là một so khớp (một kết nối), thì trả về chỉ mục của phần tử, và thoát. Bước 3 : Nếu không phải là một so khớp, thì là vị trí dò. Bước 4 : Chia danh sách bởi sử dụng phép tính tìm vị trí dò và tìm vị trí giữa mới. Bước 5 : Nếu dữ liệu cần tìm lớn hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên phải. Bước 6 : Nếu dữ liệu cần tìm nhỏ hơn giá trị tại vị trí giữa, thì tìm kiếm trong mảng con bên trái Bước 7 : Lặp lại cho tới khi tìm thấy so khớp
Code mẫu cho giải thuật Tìm kiếm nội suy
A → Mảng N → Kích cỡ của A X → Giá trị cần tìm hàm tìm kiếm nội suy Interpolation_Search() Gán Lo → 0 Gán Mid → -1 Gán Hi → N-1 While X không so khớp if Lo bằng Hi OR A[Lo] bằng A[Hi] EXIT: Thất bại, không tìm thấy X kết thúc if Gán Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) if A[Mid] = X EXIT: Thành công, tìm thấy tại Mid else if A[Mid] < X Thiết lập Lo thành Mid+1 else if A[Mid] > X Thiết lập Hi thành Mid-1 kết thúc if kết thúc if Kết thúc While Kết thúc hàm
Theo Tutorialspoint
Bài trước: Giải thuật tìm kiếm nhị phân (Binary Search)
Bài tiếp: Cấu trúc dữ liệu Hash Table
Bạn nên đọc
-
Công thức tính tỉ số thể tích các khối đa diện
-
Công thức tính diện tích tam giác: vuông, thường, cân, đều
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Công thức tính diện tích hình chóp
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

- Code NgầuThích · Phản hồi · 2 · 17/08/20
Cũ vẫn chất
-
Hàm SUMIFS, cách dùng hàm tính tổng nhiều điều kiện trong Excel
Hôm qua 8 -
Hướng dẫn hủy SMS Banking VietinBank rất đơn giản
Hôm qua -
Những bài thơ đám cưới, thơ chúc mừng đám cưới cực hay và hài hước
Hôm qua -
Lệnh UPDATE trong SQL
Hôm qua 1 -
3 cách hiển thị mật khẩu *** trên trình duyệt vô cùng đơn giản
Hôm qua -
Điều kiện LIKE trong SQL Server
Hôm qua -
Cách tắt nguồn, khởi động lại Samsung Galaxy S22, S21 và S20
Hôm qua -
Top phần mềm antivirus miễn phí cho Windows
Hôm qua -
Hướng dẫn ẩn kỷ niệm trên Facebook
Hôm qua -
Cách chèn trích dẫn trong Google Docs
Hôm qua