Bài toán nội suy cao độ 1 điểm thuật toán năm 2024
) là một thuật toán được ưu chuộng sử dụng vì tốc độ tìm kiếm rất nhanh và chính xác. Trong bài viết này chúng ta cùng nhau tìm hiểu về thuật toán này và cách triển khai nó trong ngôn ngữ JavaScript nhé. Tìm kiếm nhị phânInterpolation Search là một giải thuật tìm kiếm nhanh, một biến thể cải tiến của tìm kiếm nhị phân (Binary Search). 2 giải thuật tìm kiếm này đều dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật thực hiện được thì mảng đầu vào cần phải được sắp xếp sẵn từ trước. Để hiểu về tìm kiếm nội suy, trước tiên chúng ta tìm hiểu Binary Search nhé. Tìm kiếm nhị phân sẽ tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử cần tìm với phần tử ở vị trí giữa (theo chỉ số) của mảng đầu vào:
Ở ví dụ trên, chúng ta tìm kiếm giá trị 2 trong mảng số từ 1 đến 10. Sẽ có 4 vòng lặp được thực hiện để tìm ra được giá trị cần tìm. Ở trong ví dụ của tìm kiếm nhị phân chúng ta thấy rằng giải thuật không quan tâm đến giá trị đầu vào và luôn luôn chia đều mảng thành 2 phần bằng nhau. Thực tế nếu chúng ta đánh giá mảng số đầu vào cùng giá trị tìm kiếm thì có thể nhận thấy giá trị 2 sẽ có nhiều khả năng nằm ở vị trí đầu của mảng số vì nó gần hơn với giá trị bé nhất của mảng là 1 hơn là giá trị lớn nhất của mảng là 10. Nó cũng giống như việc khi chúng ta tra cứu từ điển, nếu cần tra cứu từ “Interpolation” thì chúng ta sẽ ưu tiên mở phần đầu của quyển từ điển hơn (do chữ cái I nằm gần đầu trong bảng chữ cái, cũng là thứ tự sắp xếp của quyển từ điển); ngược lại khi tra cứu từ “Search” thì ưu tiên sẽ là mở đến những trang gần cuối hơn. Từ ý tưởng này, tìm kiếm nội suy cải tiến tìm kiếm nhị phân bằng cách tính toán trước vị trí dò trong mảng dựa trên giá trị cần tìm theo công thức: Trong đó:
Chúng ta cùng đi vào ví dụ cụ thể nhé: Cho mảng số đã được sắp xếp như dưới đây, chúng ta cần tìm kiếm giá trị 18 trong mảng. Tìm kiếm nội suy sẽ thực hiện các vòng lặp, với mỗi vòng lặp chúng ta có 2 bước như sau: Bước 1: Tính toán chỉ số mảng cần so sánh theo công thức Bước 2: So sánh giá trị cần tìm và phần tử trong mảng theo chỉ số tính toán
Về cơ bản thì điểm khác nhau duy nhất giữa tìm kiếm nội suy và tìm kiếm nhị phân chính là bước 1. Với bài toán trên, giải thuật tìm kiếm nội suy sẽ cần chạy qua 2 vòng lặp như dưới đây: Vòng lặp đầu tiên, theo công thức thì mid sẽ cho giá trị được làm tròn là Vòng lặp thứ 2, mid = 4 + (18 – 18) * (14 – 4) / (47 – 18) = 0 Kết quả trả về đúng giá trị cần tìm ở vị trí thứ 4 của mảng. Tham khảo việc làm JavaScript tại Hồ Chí Minh trên TopDev Triển khai thuật toán trong JavaScriptTìm kiếm nội suy có cách triển khai trong JavaScript khá đơn giản và dễ hiểu, bạn có thể tham khảo đoạn code dưới đây: function interpolationSearch(sortedArray, seekElement) { let leftIndex = 0; let rightIndex = sortedArray.length - 1; while (leftIndex <= rightIndex) { const rangeDelta = sortedArray[rightIndex] - sortedArray[leftIndex]; const indexDelta = rightIndex - leftIndex; const valueDelta = seekElement - sortedArray[leftIndex]; if (valueDelta < 0) { return -1; } if (!rangeDelta) { return sortedArray[leftIndex] === seekElement ? leftIndex : -1; } // Tính toán giá trị chỉ số của mảng cần so sánh const middleIndex = leftIndex + Math.floor((valueDelta * indexDelta) / rangeDelta); // trả kết quả nếu tìm được giá trị cần tìm if (sortedArray[middleIndex] === seekElement) { return middleIndex; } if (sortedArray[middleIndex] < seekElement) { // sử dụng mảng bên phải leftIndex = middleIndex + 1; } else { // sử dụng mảng bên trái rightIndex = middleIndex - 1; } } return -1; } Độ phức tạp của thuật toánTìm kiếm nội suy có độ phức tạp là O(log(log(n))) so với tìm kiếm nhị phân với độ phức tạp là O(log(n)) thì việc cải tiến này khá đáng giá. Giải thuật cũng sẽ hiệu quả hơn với những bài toán mà các phần tử trong mảng được phân bố đều. Kết bàiNhư vậy là chúng ta đã cùng nhau tìm hiểu thuật toán tìm kiếm nội suy Interpolation Search và cách triển khai thuật toán này trong ngôn ngữ lập trình JavaScript. Đây là một thuật toán hay và cũng dễ triển khai trong nhiều ngôn ngữ lập trình khác nhau. Hy vọng bài viết hữu ích dành cho bạn và hẹn gặp lại trong các bài viết tiếp theo của mình. |